Applied Math Seminar: Johannes Brust (UCSD)

Title: PLSS: A Projected Linear Systems Solver (joint work with Michael Saunders)

Abstract:
Iteratively solving linear systems has proven to be useful for many large applications. Projection methods use sketching matrices (possibly randomized) to generate a sequence of small projected subproblems, but even the smaller systems can be costly. We develop a method in which one column is added to the sketching matrix each iteration. By choosing the sequence of all previous residuals for a sketch, we derive an iterative process with orthogonal residuals that leads to a simple recursive update to approximate the solution. In exact arithmetic, our method (PLSS) converges in at most \(n\) iterations, where \(n\) is the column rank of matrix \(A\). In experiments on large sparse systems, PLSS compares favorably with deterministic and state-of-the-art randomized methods.