Article

Impact of Accuracy Optimization on the Convergence of Numerical IterativeźMethods

Authors:

Nasrine Damouche,

Matthieu Martel,

Alexandre ChapoutotAuthors Info & Claims

LOPSTR 2015: Revised Selected Papers of the 25th International Symposium on Logic-Based Program Synthesis and Transformation - Volume 9527

Pages 143 - 160

https://doi.org/10.1007/978-3-319-27436-2_9

Published: 13 July 2015 Publication History

Abstract

Among other objectives, rewriting programs serves as a useful technique to improve numerical accuracy. However, this optimization is not intuitive and this is why we switch to automatic transformation techniques. We are interested in the optimization of numerical programs relying on the IEEE754 floating-point arithmetic. In this article, our main contribution is to study the impact of optimizing the numerical accuracy of programs on the time required by numerical iterative methods to converge. To emphasize the usefulness of our tool, we make it optimize several examples of numerical methods such as Jacobi's method, Newton-Raphson's method, etc. We show that significant speedups are obtained in terms of number of iterations, time and flops.

References

[1]

Abdelmalek, N.: Roundoff error analysis for gram-schmidt method and solution of linear least squares problem. BIT 11, 345---368 1971

[2]

ANSI/IEEE. IEEE Standard for Binary Floating-point Arithmetic, std 754---2008 second edn 2008

[3]

Benz, F., Hildebrandt, A., Hack, S.: A dynamic program analysis to find floating-point accuracy problems. In: PLDI 2012, pp. 453---462. ACM 2012

Digital Library

[4]

Consel, C., Danvy, O.: Partial evaluation of pattern matching in strings. Inf. Proc. Lett. 302, 79---86 1989

Digital Library

[5]

Cousot, P., Cousot, R.: Abstract interpretation: a unified lattice model for static analysis of programs by construction of approximations of fixed points. In: POPL 1977, pp. 238---252. ACM 1977

Digital Library

[6]

Cousot, P., Cousot, R.: Systematic design of program transformation frameworks by abstract interpretation. In: POPL 2002, pp. 178---190. ACM 2002

Digital Library

[7]

Cytron, R., Gershbein, R.: Efficient accomodation of may-alias information in SSA form. In: PLDI 1993, pp. 36---45. ACM 1993

Digital Library

[8]

Damouche, N., Martel, M., Chapoutot, A.: Intra-procedural optimization of the numerical accuracy of programs. In: Núñez, M., Güdemann, M. eds. Formal Methods for Industrial Critical Systems. LNCS, vol. 9128, pp. 31---46. Springer, Heidelberg 2015

[9]

Damouche, N., Martel, M., Chapoutot, A.: Optimizing the accuracy of a rocket trajectory simulation by program transformation. In: Computing Frontiers, pp. 40:1---40:2. ACM 2015

Digital Library

[10]

Golub, G.H., van Loan, C.F.: Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore 1996

Digital Library

[11]

Goubault, E., Putot, S.: Static analysis of finite precision computations. In: Jhala, R., Schmidt, D. eds. VMCAI 2011. LNCS, vol. 6538, pp. 232---247. Springer, Heidelberg 2011

Digital Library

[12]

Hankin, E.: Lambda Calculi A Guide For Computer Scientists. Clarendon Press, Oxford 1994

[13]

Hernandez, V., Roman, J.E., Tomas, A., Vidal, V.: Orthogonalization routine in SLEPc Technical Report STR-1. In: Polytechnic University of Valencia. STR1 2007

[14]

Hunt, S., Sands, D.: Binding time analysis: a new perspective. In: PEPM 1991, pp. 154---165 1991

Digital Library

[15]

Ioualalen, A., Martel, M.: A new abstract domain for the representation of mathematically equivalent expressions. In: Miné, A., Schmidt, D. eds. SAS 2012. LNCS, vol. 7460, pp. 75---93. Springer, Heidelberg 2012

Digital Library

[16]

Jones, N.D., Gomard, C.K., Sestoft, P.: Partial Evaluation and Automatic Program Generation. Prentice Hall International, Englewood Cliffs 1993. ISBN 0-13-020249-5

Digital Library

[17]

Kendall, A.: An Introduction to Numerical Analysis. John Wiley & Sons, New York 1989

[18]

Langlois, Ph., Louvet, N.: How to ensure a faithful polynomial evaluation with the compensated horner algorithm. In: ARITH-18, pp. 141---149. IEEE Computer Society 2007

Digital Library

[19]

Martel, M.: Semantics of roundoff error propagation in finite precision calculations. Higher-Order Symbolic Comput. 191, 7---30 2006

Digital Library

[20]

Martel, M.: Accurate evaluation of arithmetic expressions invited talk. Electr. Notes Theor. Comput. Sci. 287, 3---16 2012

Digital Library

[21]

Mouilleron, C.: Efficient computation with structured matrices and arithmetic expressions. Ph.D. thesis, Université de Lyon-ENS de Lyon, November 2011

[22]

Muller, G., Volanschi, E.-N., Marlet, R.: Scaling up partial evaluation for optimizing the sun commercial RPC protocol. In: PEPM 1997, pp. 116---126. ACM 1997

Digital Library

[23]

Muller, J.-M., Brisebarre, N., de Dinechin, F., Jeannerod, C.-P., Lefèvre, V., Melquiond, G., Revol, N., Stehlé, D., Torres, S.: Handbook of Floating-Point Arithmetic, Birkhäuser Boston 2010

Digital Library

[24]

Tate, R., Stepp, M., Tatlock, Z., Lerner, S.: Equality saturation: a new approach to optimization. In: POPL 2009, pp. 264---276. ACM 2009

Digital Library

[25]

Tate, R., Stepp, M., Tatlock, Z., Lerner, S.: Equality saturation: a new approach to optimization. Log. Meth. Comput. Sci. 71, 1---37 2011

Cited By

Benmouhoub FGaroche PMartel M(2021)An Efficient Summation Algorithm for the Accuracy, Convergence and Reproducibility of Parallel Numerical MethodsSoftware Verification10.1007/978-3-030-95561-8_10(165-181)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1007/978-3-030-95561-8_10
Damouche NMartel MChapoutot A(2017)Improving the numerical accuracy of programs by automatic transformationInternational Journal on Software Tools for Technology Transfer (STTT)10.1007/s10009-016-0435-019:4(427-448)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1007/s10009-016-0435-0

Index Terms

Impact of Accuracy Optimization on the Convergence of Numerical IterativeźMethods
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Numerical differentiation
2. Theory of computation
  1. Design and analysis of algorithms

Index terms have been assigned to the content through auto-classification.

Recommendations

On calculating the rate of linear convergence of non-linear transformed sequences
SNC '11: Proceedings of the 2011 International Workshop on Symbolic-Numeric Computation

In this paper we calculate the rate of linear convergence of non-linear transformed sequences. Using symbolic computation new results are derived which quantify the convergence acceleration effects of the Aitken transformation S, the iterated Aitken ...
Improving the numerical accuracy of programs by automatic transformation

The dangers of programs performing floating-point computations are well known. This is due to the sensitivity of the results to the way formulæ are written. These last years, several techniques have been proposed concerning the transformation of ...
Convergence of the BFGS Method for LC¹ Convex Constrained Optimization

This paper proposes a BFGS-SQP method for linearly constrained optimization where the objective function $f$ is required only to have a Lipschitz gradient. The Karush--Kuhn--Tucker system of the problem is equivalent to a system of nonsmooth equations $...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

LOPSTR 2015: Revised Selected Papers of the 25th International Symposium on Logic-Based Program Synthesis and Transformation - Volume 9527

July 2015

356 pages

ISBN:9783319274355

Editor:
Moreno Falaschi
Universití di Siena, Siena, Italy

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 13 July 2015

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Benmouhoub FGaroche PMartel M(2021)An Efficient Summation Algorithm for the Accuracy, Convergence and Reproducibility of Parallel Numerical MethodsSoftware Verification10.1007/978-3-030-95561-8_10(165-181)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1007/978-3-030-95561-8_10
Damouche NMartel MChapoutot A(2017)Improving the numerical accuracy of programs by automatic transformationInternational Journal on Software Tools for Technology Transfer (STTT)10.1007/s10009-016-0435-019:4(427-448)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1007/s10009-016-0435-0

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents