engleski

Efficient algorithms for solving shifted systems with multiple right–hand sides

We offer an efficient algorithm for solving shifted systems with multiple right sides, and for large number of shifts. This problems appears in control theory when frequency response matrix of a system is required, or when numerical solution of large linear system of ODE’s is sought. The algorithm is based on two steps. The first step reduces matrix and right–hand side of the system to a suitable form, and this is done only once. This suitable form enables us to solve the system simply and quickly. The second step repeatedly solves the systems for different shifts. We distinguish two cases of the shifted systems with m right–hand sides. • (A − σI)X = B where I is the identity matrix. In this case A is reduced to m-Hessenberg form and B is reduced to triangular form, and these reductions are done simultaneously in the first step. • (A − σE)X = B where E is a general matrix. In this case A is reduced to m-Hessenberg form and B and E are reduced to triangular form. All these reductions are done simultaneously in the first step, too. In both cases we will obtain a linear system with the m-Hessenberg system matrix and the triangular right–hand side, which is easily solved by annihilating m subdi- agonals of the system matrix. For efficiency of the algorithm the triangular form of the right–hand side is very important when the number of shifts is large. All steps of the algorithm are properly blocked to produce optimal efficiency.

Hessenberg form ; shifted linear systems ; efficient algorithms

nije evidentirano