Computational Complexity and Numerical Stability of Linear Problems

MaRDI QIDQ3567819zbMATH OpenFDO

Authors Noam Shomron, Olga Holtz

Publication date 17 June 2010

Full work available at URL https://arxiv.org/abs/0906.0687

zbMATH Keywords

arithmetic complexityarithmetic operationsasymptotic complexitybilinear algorithmsbit operationsborder rankclassical model of arithmeticFourier transformgroup algebrasLU decompositionmatrix inversionmatrix multiplicationmultiplicative complexitynumerical stabilityQR decompositionrank revealing decompositionroundoff errorSchur formStrassen's algorithmSylvester equationtensor ranktensorswreath product

Mathematics Subject Classification ID

Numerical linear algebra (65Fxx) Roundoff error (65G50) Complexity and performance of numerical algorithms (65Y20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Abstract: We survey classical and recent developments in numerical linear algebra, focusing on two issues: computational complexity, or arithmetic costs, and numerical stability, or performance under roundoff error. We present a brief account of the algebraic complexity theory as well as the general error analysis for matrix multiplication and related problems. We emphasize the central role played by the matrix multiplication problem and discuss historical and modern approaches to its solution.

Recommendations

• Complexity theory of numerical linear algebra
• The computational complexity of some problems of linear algebra
• scientific article; zbMATH DE number 4215257
• On numerical stability in large scale linear algebraic computations
• Numerical analysis on linear complementarity problems
• scientific article; zbMATH DE number 2078353
• Computability in linear algebra
• scientific article; zbMATH DE number 3581612
• The computational complexity of some problems of linear algebra (extended abstract)
• scientific article; zbMATH DE number 3936517

Cited in

(10)

• Complexity theory of numerical linear algebra
• Computational complexity of real powering and improved solving linear differential equations
• scientific article; zbMATH DE number 3872554 (Why is no real title available?)
• Complexity of Solving Linear Systems in Different Models of Computation
• scientific article; zbMATH DE number 17440 (Why is no real title available?)
• scientific article; zbMATH DE number 65652 (Why is no real title available?)
• scientific article; zbMATH DE number 3581612 (Why is no real title available?)
• scientific article; zbMATH DE number 2078353 (Why is no real title available?)
• On numerical stability in large scale linear algebraic computations
• Open problems in computational linear algebra

Describes a project that uses

Uses Software

• ScaLAPACK

This page was built for publication: Computational Complexity and Numerical Stability of Linear Problems

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