COMPUTATIONS WITH STRUCTURED MATRICES

VICTOR Y. PAN BRIAN MURPHY RHYS ERIC ROSHOLT

Abstract. We review some basic algorithms for solving problems expressed in the form of matrix equations. The algorithms, which include block Gaussian elimination and recursive block triangular factorization, are first shown for general matrices and then extended to structured matrices, in which case they run much faster and use much less computer memory. In particular, we review the solution of structured linear systems and recall some recent results on the computations with singular structured matrices and on iterative improvement of approximate solutions by using residual correction/Newton’s iteration techniques.