engleski

Efficient Algorithm for Simultaneous Reduction to the m-Hessenberg–Triangular–Triangular Form

This paper proposes an efficient algorithm for simultaneous reduction of three matrices. The algorithm is a blocked version of the algorithm described by Miminis and Page (1982) which reduces A to the m-Hessenberg form, and B and E to the triangular form. The m-Hessenberg--triangular--triangular form of matrices A, B and E 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 discretization of the time-harmonic wave equation in heterogeneous media, or originate from structural dynamics engineering problems. The proposed blocked algorithm for the m-Hessenberg--triangular--triangular reduction is based on the aggregated Givens rotations, which are a generalization of the blocked algorithm for the Hessenberg--triangular reduction proposed by Kagstrom et al. (2008). Numerical tests confirmed that the blocked algorithm is up to 3.4 times faster than its non-blocked version based on regular Givens rotations only. As an illustration of its efficiency, two applications of the m-Hessenberg--triangular--triangular reduction coming 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.

m-Hessenberg–triangular–triangular form ;
orthogonal transformations ;
level 3 BLAS ;
blocked algorithm ;
solving shifted system ;
transfer function evaluation ;
staircase form

nije evidentirano