The complexity of the matrix eigenproblem

DOI10.1145/301250.301389zbMath1346.68103OpenAlexW2091075671MaRDI QIDQ2819583

No author found.

Publication date: 29 September 2016

Published in: Proceedings of the thirty-first annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/301250.301389

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Eigenvalues, singular values, and eigenvectors (15A18) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (30)

Stochastic semidiscretization method: second moment stability analysis of linear stochastic periodic dynamical systems with delays ⋮ First-order continuous- and discontinuous-Galerkin moment models for a linear kinetic equation: realizability-preserving splitting scheme and numerical analysis ⋮ Bounds on skyline probability for databases with uncertain preferences ⋮ AMID: approximation of multi-measured data using SVD ⋮ Computing the asymptotic distribution of second-order \(U\)- and \(V\)-statistics ⋮ New spectral bounds on \(\mathcal{H}_2\)-norm of linear dynamical networks ⋮ Algebraic connectivity of network-of-networks having a graph product structure ⋮ The robust minimal controllability problem ⋮ The Complexity of Diagonalization ⋮ Learning methods for structural damage detection via entropy‐based sensors selection ⋮ Landmark diffusion maps (L-dMaps): accelerated manifold learning out-of-sample extension ⋮ Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time ⋮ Constrained polynomial zonotopes ⋮ Dynamic normal forms and dynamic characteristic polynomial ⋮ A new trust region technique for the maximum weight clique problem ⋮ An adaptive local reduced basis method for solving PDEs with uncertain inputs and evaluating risk ⋮ An SDP primal-dual algorithm for approximating the Lovász-theta function ⋮ Distributed resource allocation with binary decisions via Newton-like neural network dynamics ⋮ A feasible \(k\)-means kernel trick under non-Euclidean feature space ⋮ An Ellipsoidal Bounding Scheme for the Quasi-Clique Number of a Graph ⋮ High-performance processing of covariance matrices using GPU computations ⋮ Multilevel Artificial Neural Network Training for Spatially Correlated Learning ⋮ Bit complexity of computing solutions for symmetric hyperbolic systems of PDEs with guaranteed precision ⋮ An approximation algorithm for the maximum spectral subgraph problem ⋮ Eigenvalue-flipping algorithm for matrix Monte Carlo ⋮ Typical case complexity of satisfiability algorithms and the threshold phenomenon ⋮ On eventual non-negativity and positivity for the weighted sum of powers of matrices ⋮ Encoding inductive invariants as barrier certificates: synthesis via difference-of-convex programming ⋮ Hermitian matrix definiteness from quantum phase estimation ⋮ Distributionally Robust Inverse Covariance Estimation: The Wasserstein Shrinkage Estimator

This page was built for publication: The complexity of the matrix eigenproblem