230
M. Tsuji et.al.
6.1 Implicitly Restarted Arnoldi Method (IRAM), Multiple
Implicitly Restarted Arnoldi Method (MIRAM) and Their
Implementations for the mSPMD Programming Model
The iterative methods are widely used to solve eigenvalue programs in scientific
computation. Implicitly Restarted Arnoldi Method (IRAM) [10] is one of the
iterative methods to search the eigen elements λ s.t. Ax = λx of a matrix A.
Figure 10 shows the algorithm of IRAM. IRAM is a technique that combines
the implicitly shifted QR mechanism with an Arnoldi factorization and the IRAM
can be viewed as a truncated form of the implicitly shifted QR-iteration. After the
first m-step Arnoldi factorization, the eigen pairs of a Heisenberg matrix H are
computed. If the residual norm is small enough, the iteration is stopped. Otherwise,
the shifted QR by selecting shifts based on eigenvalues of the Heisenberg matrix
is computed. Using these new vectors and H as a starting point, we can apply p
additional steps of the Arnoldi process to obtain an m-step Arnoldi factorization.
Multiple IRAM (MIRAM) is an extension of IRAM, which introduces two or
more instances of IRAM. The instances of IRAM work on the same problem, but
they are initialized with different subspaces m 1 , m 2 , · · · . At the restarting point,
each instance selects the best (m best , H best , V best , f best ) from l IRAM instances.
In the mSPMD programming model, MIRAM has been implemented, as shown
in Fig. 11. The source code written in YvetteML is shown in Fig. 12. The YML
workflow scheduler invokes l IRAM instances and a data server. Each of IRAM
Fig. 10 Algorithm of IRAM
M. Tsuji et.al.
6.1 Implicitly Restarted Arnoldi Method (IRAM), Multiple
Implicitly Restarted Arnoldi Method (MIRAM) and Their
Implementations for the mSPMD Programming Model
The iterative methods are widely used to solve eigenvalue programs in scientific
computation. Implicitly Restarted Arnoldi Method (IRAM) [10] is one of the
iterative methods to search the eigen elements λ s.t. Ax = λx of a matrix A.
Figure 10 shows the algorithm of IRAM. IRAM is a technique that combines
the implicitly shifted QR mechanism with an Arnoldi factorization and the IRAM
can be viewed as a truncated form of the implicitly shifted QR-iteration. After the
first m-step Arnoldi factorization, the eigen pairs of a Heisenberg matrix H are
computed. If the residual norm is small enough, the iteration is stopped. Otherwise,
the shifted QR by selecting shifts based on eigenvalues of the Heisenberg matrix
is computed. Using these new vectors and H as a starting point, we can apply p
additional steps of the Arnoldi process to obtain an m-step Arnoldi factorization.
Multiple IRAM (MIRAM) is an extension of IRAM, which introduces two or
more instances of IRAM. The instances of IRAM work on the same problem, but
they are initialized with different subspaces m 1 , m 2 , · · · . At the restarting point,
each instance selects the best (m best , H best , V best , f best ) from l IRAM instances.
In the mSPMD programming model, MIRAM has been implemented, as shown
in Fig. 11. The source code written in YvetteML is shown in Fig. 12. The YML
workflow scheduler invokes l IRAM instances and a data server. Each of IRAM
Fig. 10 Algorithm of IRAM