Inverse Iteration - Implementation Options

Implementation Options

The method is defined by the formula:

There are several details in its implementation.

• Calculate inverse matrix or solve system of linear equations.

We can rewrite the formula in the following way:

emphasizing that to find the next approximation we need to solve a system of linear equations. There are two options: one may choose an algorithm that solves a linear system, or to calculate an inverse matrix and then apply it to the vector. Both options have complexity O(n3), the exact number depends on the chosen method. Typically, solutions of linear equation have slightly less complexity. The choice between the options depends on the number of iterations. If one solves the linear system the complexity will be k*O(n3), where k is number of iterations. Calculating the inverse matrix first and then applying it to the vectors b_k is of complexity O(n3) + k* n2. The second option is clearly preferable for large numbers of iterations. As inverse iterations are typically used when only a small number of iterations is needed one usually solves a linear system of equations.

• Tridiagonalization, Hessenberg form.

If it is necessary to perform many iterations (or few iterations, but for many eigenvectors), then it might be wise to bring the matrix to the upper Hessenberg form first (for symmetric matrix this will be tridiagonal form). Which costs arithmetic operations using a technique based on Householder reduction), with a finite sequence of orthogonal similarity transforms, somewhat like a two-sided QR decomposition. (For QR decomposition, the Householder rotations are multiplied only on the left, but for the Hessenberg case they are multiplied on both left and right.) For symmetric matrices this procedure costs arithmetic operations using a technique based on Householder reduction.

Solution of the system of linear equations for the tridiagonal matrix costs O(n) operations, so the complexity grows like O(n3)+k*O(n), where k is an iteration number, which is better than for the direct inversion. However for small number of iterations such transformation may not be practical.

Also transformation to the Hessenberg form involves square roots and division operation, which are not hardware supported on some equipment like digital signal processors, FPGA, ASIC.

• Choice of the normalization constant C_k and avoiding division.

On general purpose processors (e.g. produced by Intel) the execution time of addition, multiplication and division is approximately the same. But fast and/or low energy consuming hardware (digital signal processors, FPGA, ASIC) division is not supported by hardware, and so should be avoided. For such hardware it is recommended to use C_k=2n_k, since division by powers of 2 is implemented by bit shift and supported on any hardware.

The same hardware usually supports only fixed point arithmetics: essentially works with integers. So the choice of the constant C_k is especially important - taking too small value will lead to fast growth of the norm of b_k and to the overflow; for too big C_k vector b_k will tend to zero. The optimal value of C_k is the eigenvalue of the corresponding eigenvector. So one should choose C_k approximately the same.