Efficient algorithm for simultaneous reduction to the m-Hessenberg-triangular-triangular form

摘要

This paper proposes an efficient algorithm for simultaneous reduction of three matrices by using orthogonal transformations, where is reduced to -Hessenberg form, and and to triangular form. The algorithm is a blocked version of the algorithm described by Miminis and Paige (Int J Control 35:341-354, 1982). The -Hessenberg-triangular-triangular form of matrices , and is specially suitable for solving multiple shifted systems . Such shifted systems naturally occur in control theory when evaluating the transfer function of a descriptor system, or in interpolatory model reduction methods. They also arise as a result of discretizing the time-harmonic wave equation in heterogeneous media, or originate from structural dynamics engineering problems. The proposed blocked algorithm for the -Hessenberg-triangular-triangular reduction is based on aggregated Givens rotations, and is a generalization of the blocked algorithm for the Hessenberg-triangular reduction proposed by KAyengstrom et al. (BIT 48:563-584, 2008). Numerical tests confirm that the blocked algorithm is much faster than its non-blocked version based on regular Givens rotations only. As an illustration of its efficiency, two applications of the -Hessenberg-triangular-triangular reduction from control theory are described: evaluation of the transfer function of a descriptor system at many complex values, and computation of the staircase form used to identify the controllable part of the system.