engleski

Fast Algorithm for Computing the Condensed Form of Four Matrices for the VZ Algorithm

Charles F. Van Loan in 1975 proposes a general QR-type process called the VZ algorithm for the solution of the general matrix eigenvalue problem A*C*x=lambda B*D*x. Especially, this algorithm is suitable for solving the generalized singular value problem. The main point of the discussion presented in this article is that transforming the general eigenvalue problem to the standard form represents a possible numerical danger. The formation of the products, as well as the formation of the inverse can produce a result with a large backward error. Thus, the VZ algorithm attempts to solve the general eigenvalue problem without forming these products and inverse. This approach transforms each of the four matrices separately into a desired form. Actually, the algorithm computes orthogonal matrices Q, U, V, and Z such that Q*A*Z is upper quasi-triangular, and Q*B*V, Z^T*C*U and V^T*D*U are upper triangular. The VZ algorithm begins by reducing the matrices A, B, C, and D to an equivalent condensed form by the finite step initial reduction. This reduction finds orthogonal matrices Q0, U0, V0 and Z0, such that Q0*A*Z0 is upper Hessenberg, and Q0*B*V0, Z0^T*C*U0 and V0^T*D*U0 are upper triangular. Then, the VZ iterations are applied to the matrices in the condensed form. As Van Loan pointed out, while the VZ algorithm can successfully solve the generalized singular value problem, even in pathological situations, it does have the drawback of being very inefficient. In the initial reduction, A is reduced to the upper Hessenberg form, while simultaneously preserving triangularity of the other three matrices. This is done by the Givens rotations, annihilating one by one element of A, and by generating three more rotations applied to the other matrices per each annihilation. Such an algorithm is quite inefficient. In our work, we propose a blocked algorithm for the initial reduction, which is a generalization of the blocked algorithm for the m-Hessenberg-triangular-triangular reduction proposed by N. Bosner in 2014, and the blocked algorithm for the Hessenberg-triangular reduction proposed by B. Kagstro}; ; m, D. Kressner, E. S. Quintana-Orti, and G. Quintana-Orti in 2008. These blocked algorithms are based on the aggregated Givens rotations, which are applied in the outer loop updates. The blocked algorithm for the initial reduction has another level of blocking, exploited in the inner loop updates, since there is a larger number of matrices involved in these updates. Preliminary tests confirmed, that our blocked algorithm is up to 2.7 times faster than the original algorithm for the initial reduction when orthogonal factors are not computed, and over 4 times faster when orthogonal factors are accumulated. This way the efficiency of the whole VZ algorithm is increased. In the future work, we plan to generalize the efficient version of the QR iterations proposed by F. G. Van Zee, R. van de Geijn, and G. Quintana-Orti in 2014 to the VZ iterations, which will produce an efficient and accurate algorithm for solving general eigenvalue problem.

efficient blocked algorithm ; Hessenberg-triangular-triangular-triangular reduction ; VZ algorithm ; general eigenvalue problem

nije evidentirano