On speed versus accuracy: Some case studies

DOI10.1006/JCOM.1996.0016MaRDI QIDQ2565199zbMATH OpenOpenAlexFDO

Authors Mauro Leoncini

Publication date 27 July 1997

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcom.1996.0016

zbMATH Keywords

algorithmscomplexitydeterminanterror boundsPLU decompositionpolynomial evaluationstability

Mathematics Subject Classification ID

Computation of special functions and constants, construction of tables (65D20) Direct numerical methods for linear systems and matrix inversion (65F05) Numerical computation of determinants (65F40) Complexity and performance of numerical algorithms (65Y20) Analysis of algorithms and problem complexity (68Q25)

Review text

Following the author's words, usually the error bounds obtained for the fastest algorithms are much worse than the bounds known for the corresponding classical algorithms. As a counterargument, one can state that good accuracy can be obtained under a reasonable theoretical model of arithmetic. The paper explores the suitability of complexity theoretic tools to deal with accuracy issues. This is done for significant examples corresponding to three different settings: sequential complexity, parallel complexity and relative complexity of problems. For the sequential setting the (linear) problem of polynomial evaluation at many (fixed) points is studied; it is proved that the fastest known algorithms are not stable. The PLU decomposition of a real matrix is regarded in the parallel setting. The author establishes that certain constraints on the computed factors which imply good accuracy make the PLU decomposition hard to solve in parallel. Finally, an example of computation of a determinant using an oracle for the characteristic polynomial is considered. In this case, the same stability constraints discussed for the problem of polynomial evaluation are violated. The conclusion is that reductions among computational problems do not in general constitute a practical tool for solving numerical problems.

Recommendations

• Some results on speed-up
• Combining speed and accuracy to assess error-free cognitive processes
• Truth and speed-up
• Complexity in the case against accuracy estimation

Cited in

(5)

• Parallel algebraic reductions among numerical problems
• Oracle computations in parallel numerical linear algebra
• The correction of a formula in the speed-accuracy decomposition technique of Meyer, Irwin, Osman, and Kounios (1988).
• Ultimate complexity for numerical algorithms
• Stability versus speed in a computable algebraic model

This page was built for publication: On speed versus accuracy: Some case studies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2565199)