학술논문
PLSS: a projected linear systems solver.
Document Type
Journal
Author
Brust, Johannes J. (1-UCSD) AMS Author Profile; Saunders, Michael A. (1-STF-MGE) AMS Author Profile
Source
Subject
15 Linear and multilinear algebra; matrix theory -- 15A Basic linear algebra
15A06Linear equations
15Linear and multilinear algebra; matrix theory -- 15B Special matrices
15B52Random matrices
65Numerical analysis -- 65Y Computer aspects of numerical algorithms
65Y20Complexity and performance of numerical algorithms
90Operations research, mathematical programming -- 90C Mathematical programming
90C20Quadratic programming
15A06
15
15B52
65
65Y20
90
90C20
Language
English
Abstract
Summary: ``We propose iterative projection methods for solving square or rectangular consistent linear systems $\bf Ax = b$. Existing 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 process that appends one column to the sketching matrix each iteration and converges in a finite number of iterations whether the sketch is random or deterministic. In general, our process generates orthogonal updates to the approximate solution ${\bf x}_k$. By choosing the sketch to be the set of all previous residuals, we obtain a simple recursive update and convergence in at most rank$(\bf A)$ iterations (in exact arithmetic). By choosing a sequence of identity columns for the sketch, we develop a generalization of the Kaczmarz method. In experiments on large sparse systems, our method (PLSS) with residual sketches is competitive with LSQR and LSMR and with residual and identity sketches compares favorably with state-of-the-art randomized methods.''MR