Resumen de Structured condition numbers for parameterized quasiseparable matrices
Kenet Jorge Pomés Portal
Low-rank structured matrices have attracted much attention in the last decades, since they arise in many applications and all share the fundamental property that can be represented by O(n) parameters, where n × n is the size of the matrix. This property has allowed the development of fast algorithms for solving numerically many problems involving low-rank structured matrices by performing operations on the parameters describing the matrices, instead of directly on the matrix entries. Among these problems the solution of linear systems of equations and the computation of the eigenvalues are probably the most basic and relevant ones. Therefore, it is important to measure, via structured computable condition numbers, the rela- tive sensitivity of the solutions of linear systems with low-rank structured coefficient matrices, and of the eigenvalues of those matrices, with respect to relative perturba- tions of the parameters representing such matrices, since this sensitivity determines the maximum accuracy attainable by fast algorithms and allows us to decide which set of parameters is the most convenient from the point of view of accuracy.
In this PhD Thesis we develop and analyze condition numbers for eigenvalues of low-rank matrices and for the solutions of linear systems involving such matrices. To this purpose, general expressions are obtained for the condition numbers of the solution of a linear system of equations whose coefficient matrix is any differentiable function of a vector of parameters with respect to perturbations of such parameters, and also for the eigenvalues of those matrices.
Since there are many different classes of low-rank structured matrices and many different types of parameters describing them, it is not possible to cover all of them in this thesis. Therefore, the general expressions of the condition numbers are particularized to the important case of quasiseparable matrices and to the quasiseparable and the Givens-vector representations. In the case of {1, 1}-quasiseparable matrices, we provide explicit expressions of the corresponding condition numbers for these two representations that can be estimated in O(n) operations. In addi- tion, detailed theoretical and numerical comparisons of the condition numbers with respect to these two representations between themselves, and with respect to un- structured condition numbers are provided. These comparisons show that there are situations in which the unstructured condition numbers are much larger than the structured ones, but that the opposite never happens. On the other hand, for general {nL, nU }-quasiseparable matrices we also present an explicit expression for comput- ing the eigenvalue condition number for the general quasiseparable representation in O(n2L + n2U )n operations. In this case, significant differences are obtained with respect to the {1, 1}-case, since if nL or nU are greater than one, then the structured condition number may be much larger than the unstructured one, which suggests the use of a more stable representation in that case. The approach presented in this dissertation can be generalized to other classes of low-rank structured matrices and parameterizations, as well as to any class of structured matrices that can be represented by parameters, independently of whether or not they enjoy a “low-rank” structure.
