Complexity theory of numerical linear algebra

DOI10.1016/0377-0427(88)90402-5MaRDI QIDQ1103328zbMATH OpenOpenAlexFDO

Authors Eric Kostlan

Publication date 1988

Published in Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-0427(88)90402-5

zbMATH Keywords

computational complexityrandom matricespower methodrandom systems

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Analysis of algorithms and problem complexity (68Q25) Numerical computation of matrix norms, conditioning, scaling (65F35)

Recommendations

• Computational Complexity and Numerical Stability of Linear Problems
• The Probability That a Numerical Analysis Problem is Difficult
• On the efficiency of algorithms of analysis
• scientific article; zbMATH DE number 7139139
• Asymptotic complexity of Monte Carlo methods for solving linear systems

Cites work

• scientific article; zbMATH DE number 3533716 (Why is no real title available?)
• scientific article; zbMATH DE number 3567411 (Why is no real title available?)
• scientific article; zbMATH DE number 1234098 (Why is no real title available?)
• scientific article; zbMATH DE number 486467 (Why is no real title available?)
• scientific article; zbMATH DE number 3277086 (Why is no real title available?)
• Evaluating Rational Functions: Infinite Precision is Finite Cost and Tractable on Average
• The fundamental theorem of algebra and complexity theory

Cited in

(24)

• Wilkinson's bus: weak condition numbers, with an application to singular polynomial eigenproblems
• The Probability That a Numerical Analysis Problem is Difficult
• Average condition number for solving linear equations
• Interval Linear Algebra and Computational Complexity
• Invertibility of random fredholm operators
• Least singular value and condition number of a square random matrix with i.i.d. rows
• Grid methods in computational real algebraic (and semialgebraic) geometry
• Average-case complexity without the black swans
• Linear complexity algorithm for semiseparable matrices
• Computational Complexity and Numerical Stability of Linear Problems
• scientific article; zbMATH DE number 2072707 (Why is no real title available?)
• Towards a common thread in complexity: an accuracy-based approach
• Computational complexity of kernel-based density-ratio estimation: a condition number analysis
• Smooth analysis of the condition number and the least singular value
• On spectral and numerical properties of random butterfly matrices
• Random matrix theory for the analysis of the performance of an analog computer: a scaling theory
• Statistical complexity of dominant eigenvector calculation
• Computing the homology of semialgebraic sets. I: Lax formulas
• Universality in numerical computation with random data: case studies and analytical results
• On the efficiency of algorithms of analysis
• The asymptotic distribution of the condition number for random circulant matrices
• Universality for Eigenvalue Algorithms on Sample Covariance Matrices
• On the volume of tubular neighborhoods of real algebraic varieties
• Computing the homology of real projective sets

This page was built for publication: Complexity theory of numerical linear algebra

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