Presented By: Applied Interdisciplinary Mathematics (AIM) Seminar  Department of Mathematics
AIM Seminar: Solving Large Linear Systems Without Constructing a Preconditioner
Michał Dereziński, EECS, University of Michigan
Abstract: Solving systems of linear equations has numerous applications across many areas, from data science and machine learning, to scientific computing, engineering and more. When these systems are too large to solve directly, iterative refinement methods such as conjugate gradient have proven to be a powerful alternative. The computational cost of these methods can be significantly affected by a problemdependent condition number, which is often addressed by combining the iterative solver with a preconditioner, i.e., an easy to invert approximation of the original system. However, constructing a good preconditioner can still be very expensive, which leads to an undesirable tradeoff between the cost of preconditioning and the cost of solving the linear system.
In this talk, I will present new stochastic iterative methods for solving linear systems based on the socalled SketchandProject paradigm, which can reduce the condition number of the system without having to precondition it. This approach is based on the following phenomenon: Whenever the spectral structure of a linear system is amenable to constructing a strong preconditioner via lowrank matrix approximation, we can design a SketchandProject solver that will implicitly take advantage of this to find the solution faster. In particular, I will show how this leads to solving an n x n linear system with at most k large (outlying) singular values in ~O( n^2 + n k^2 ) arithmetic operations, which is faster than the ~O( n^2 k ) cost of constructing a good preconditioner for this system.
Contact: Robert Krasny
In this talk, I will present new stochastic iterative methods for solving linear systems based on the socalled SketchandProject paradigm, which can reduce the condition number of the system without having to precondition it. This approach is based on the following phenomenon: Whenever the spectral structure of a linear system is amenable to constructing a strong preconditioner via lowrank matrix approximation, we can design a SketchandProject solver that will implicitly take advantage of this to find the solution faster. In particular, I will show how this leads to solving an n x n linear system with at most k large (outlying) singular values in ~O( n^2 + n k^2 ) arithmetic operations, which is faster than the ~O( n^2 k ) cost of constructing a good preconditioner for this system.
Contact: Robert Krasny
CoSponsored By
Explore Similar Events

Loading Similar Events...