Complexity theory of numerical linear algebra

DOI10.1016/0377-0427(88)90402-5zbMath0645.65019OpenAlexW2006459820MaRDI QIDQ1103328

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

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

Related Items (15)

Average-case complexity without the black swans ⋮ Smooth analysis of the condition number and the least singular value ⋮ Wilkinson's bus: weak condition numbers, with an application to singular polynomial eigenproblems ⋮ Average condition number for solving linear equations ⋮ Invertibility of random fredholm operators ⋮ Universality for Eigenvalue Algorithms on Sample Covariance Matrices ⋮ Computational complexity of kernel-based density-ratio estimation: a condition number analysis ⋮ Computing the homology of real projective sets ⋮ Statistical complexity of dominant eigenvector calculation ⋮ 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 ⋮ On the volume of tubular neighborhoods of real algebraic varieties ⋮ Computing the homology of semialgebraic sets. I: Lax formulas ⋮ The Probability That a Numerical Analysis Problem is Difficult ⋮ The asymptotic distribution of the condition number for random circulant matrices

Cites Work

• Evaluating Rational Functions: Infinite Precision is Finite Cost and Tractable on Average
• The fundamental theorem of algebra and complexity theory
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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