Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems

arXiv:2405.05818v1 Announce Type: cross
Abstract: While effective in practice, iterative methods for solving large systems of linear equations can be significantly affected by problem-dependent condition number quantities. This makes characterizing their time complexity challenging, particularly when we wish to make comparisons between deterministic and stochastic methods, that may or may not rely on preconditioning and/or fast matrix multiplication. In this work, we consider a fine-grained notion of complexity for iterative linear solvers which we call the spectral tail condition number, …

abstract algorithms analysis arxiv complexity cs.ds cs.lg cs.na faster fine-grained iterative linear math.na math.oc practice stochastic systems type while