Study On Reliable Computing And Rounding Error Analysis In Floating-point Arithmetic

In high-performance computing, large-scale and long-time numerical calculationsoften produce inaccurate and invalidated results owing to cancellation from round-offerrors. To deal with this problem, this thesis, based on error-free transformation, willanalyze the accumulative effect of round-off errors in the floating point code level. Thenthe thesis will propose several high-precision and high-efficient compensated algorithms.The main work and innovation are embodied as follows.1. This thesis presents a compensated algorithm for the evaluation of the k-th deriva-tive of a polynomial in power basis. The proposed algorithm makes it possible the directevaluation without obtaining the k-th derivative expression of the polynomial itself, withaveryaccurateresulttoallbutthemostill-conditionedevaluation. Forwarderroranalysisand running error analysis are performed by an approach based on the data dependencygraph. Numerical experiments illustrate the accuracy and efficiency of the algorithm.2. This thesis presents an application to show the effectiveness of the compensatedHorner derivative algorithm. We consider the Newton’s method in floating-point arith-metic for solving the equation of the univariate polynomial with a simple root. We usecompensatedHorneralgorithm and compensatedHornerderivativetoimprovetheclassicNewton method. The error analysis and numerical tests illustrate that the convergence ofiteration strongly depends on the accuracy of the derivative’s evaluation when the prob-lemoffindingsimplerootistooill-conditioned, andthattheaccuracyofthefinaliterationresult depends on the accuracy of the residual computed.3. In computer aided geometric design a polynomial is usually represented in Bern-stein form. This thesis presents several compensated algorithms to accurately evaluate aunivariatepolynomialinBernsteinform, abivariatepolynomialinBernstein–Bézierformand a B′ezier tensor product surfaces. The coefficients and coordinates of all the polyno-mials considered are the floating point numbers. The principle is to apply error-free trans-formation to improve traditional de Casteljau algorithms. Forward error analysis, runningerror analysis and numerical experiments illustrate the accuracy of our algorithms.4. This thesis presents a compensated algorithm to accurately evaluate a polynomialexpressed in Chebyshev basis of the first and second kind with floating-point coefficients.The principle is to apply error-free transformations to improve the traditional Clenshaw algorithm. The new algorithm is as accurate as the Clenshaw algorithm performed intwice the working precision. Forward error analysis and numerical experiments illustratethe accuracy and properties of the proposed algorithm5. This thesis is concerned with the fast and accurate evaluation of elementary sym-metric functions. We present a new compensated algorithm by applying error-free trans-formationstoimprovetheaccuracyoftheso-calledSummationAlgorithm, whichisused,by example, in the MATLAB’s poly function. We derive a forward roundoff error boundand running error bound for our new algorithm. The roundoff error bound implies that thecomputed result is as accurate as if computed with twice the working precision and thenrounded to the current working precision. The running error analysis provides a shaperbound along with the result, without increasing significantly the computational cost. Nu-mericalexperimentsillustratethatouralgorithmrunsmuchfasterthanthealgorithmusingthe classic double-double library while sharing similar error estimates. Such an algorithmcan be widely applicable for example to compute characteristic polynomials from eigen-values. It can also be used into the Rasch model in psychological measurement.