Structured eigenvalue condition numbers for parameterized quasiseparable matrices Articles uri icon

publication date

  • November 2016

start page

  • 473

end page

  • 512

issue

  • 3

volume

  • 134

International Standard Serial Number (ISSN)

  • 0029-599X

Electronic International Standard Serial Number (EISSN)

  • 0945-3245

abstract

  • The development of fast algorithms for performing computations with n n low-rank structured matrices has been a very active area of research during the last two decades, as a consequence of the numerous applications where these matrices arise. The key ideas behind these fast algorithms are that low-rank structured matrices can be described in terms of O(n) parameters and that these algorithms operate on the parameters instead on the matrix entries. Therefore, the sensitivity of any computed quantity should be measured with respect to the possible variations that the parameters de ning these matrices may su er, since this determines the maximum accuracy of a given fast computation. In other words, it is necessary to develop condition numbers with respect to parameters for di erent magnitudes and classes of low-rank structured matrices, but, as far as we know, this has not yet been accomplished in any case. In this paper, we derive structured relative eigenvalue condition numbers for the important class of low-rank structured matrices known as f1; 1g-quasiseparable matrices with respect to relative perturbations of the parameters in the quasiseparable and in the Givens-vector representations of these matrices, and we provide fast algorithms for computing them. Comparisons among the new structured condition numbers and the unstructured one are also presented, as well as numerical experiments showing that the structured condition numbers can be small in situations where the unstructured one is huge. In addition, the approach presented in this paper is general and may be extended to other problems and classes of low-rank structured matrices.

keywords

  • hierarchical matrices; companion matrices; givens rotations; algorithms; inversion; equations; solver