A control theory approach to linear equation solvers
Uwe Helmke, Jens Jordan, Alexander Lanzon · ANU Open Research (Australian National University) · 2006
We present a new iterative approach for solv- ing linear systems of equations. Our method is inspired by feedback stabilization schemes from robust control and yields a control system, whose parameters can be tuned to achieve prescribed convergence properties. In contrast to well-known iterative solution methods for linear equations from linear algebra, such as GMRES(m) or Arnoldi's method, the proposed dynamical systems solution algorithms have the advantage of being globally convergent or having tunable convergence properties. Keywords—linear equations, iterative methods, feedback control, stabilization. I. INTRODUCTION Solving linear systems of equations Ax = b or computing the inverse A −1 of a matrix are core problems of numerical linear algebra, for which powerful solution methods and software packages exist. For the inversion of moderate size matrices, standard LU or QR factorization methods work very well, but these methods are no longer applicable for large scale matrices. Krylov subspace methods such as conjugate gradient, GMRES(m) or Lanczos and Arnoldi work well for even very large systems of equations defined by positive definite symmetric or normal matrices A.H owever, the situation becomes more complicated (and interesting) in other cases. In fact, the dynamics of an iterative method such as e.g. GMRES(m) can be quite complex and is far from being fully understood. For indefinite symmetric matrices, GMRES(m) exhibit continua of non-trivial equilibrium points that may prevent the algorithm to converge to the desired solution. The situation becomes even worse for matrices far from normality, forcing the algorithm to loose fast local convergence or create even regimes of chaotic behavior in the phase space; see (1). Of course, there is no reason, why there might not exist reliable linear equation solvers that would work also in those cases where the presently known methods fail. The very structure of present iterative solution methods even points to a resolution of this issue. In fact, such iterative schemes define feedback control systems and therefore can be analyzed using tools from control