Papers - Nodera, Takashi

Effectiveness of Adaptively Left　Preconditioned GMRES(m) algorithm On Origin 20000

Hiroo Suzuki, Takashi Nodera

Proceedings of SGI User's Conference (CYFRONET, Academic Computer Centre of the University of Mining and Metallurgy)     419-428 2000.10

Research paper (scientific journal), Joint Work, Accepted

　View Summary

GMRES(m) method is one of the iterative algorithms for solving the linear systems of equations with a large, sparse, and nonsymmetric coefficient matrix. This restarted method is able to reduce both computational work and its memory requirement. However, using the restart, GMRES(m) method looses the information of some eigenvectors corresponding to the smallest eigenvalues, and its convergence may slow down or stall. In this paper, we compare the restarted GMRES(m,k,alpha,beta) method
which determines left preconditioner adaptively coupling with IRA (Implicitly Restarted Arnoldi) process. At last, we will give the numerical experiments on the parallel
machine Origin 2000 and concluding remarks.

GMRES（m） algorithm with changing the restart cycle adaptively

Mitsuru Habu, Takashi Nodera

Proceedings of Algoritmy 2000 Conference on Scientific Computing (Solvak Univ.of Tech, Bratislava, Comenius Univ., Bratislava, and Univ. of Technology, Zvolen)     254-263 2000.09

Research paper (conference, symposium, etc.), Joint Work, Accepted

　View Summary

A restarted GMRES(m) algorithm is often an effective means for solving nonsymmetric linear systems of equations. However, this algorithm sometimes experiences stagnation or slow convergence, if too small restart cycle m is chosen. Unfortunately, it can be very difficult to know how to choose m a priori. In this paper, we present new adaptive strategy which the restart cycle m can be both increases and decreased by using the tolerance of estimated number of iterations to achieve convergence. Numerical comparisons of the new algorithm and the standard one are given on the parallel computer Origin 2000. These results show that this new algorithm has a reasonable convergence rather than the other algorithms.

リスタートサイクルを適応的に変えるGMRES(k)法

Mitsuru Fabu, Takashi Nodera

情処研報 2000 ( 73 ) 47-52 2000.08

Research paper (conference, symposium, etc.), Single Work

　View Summary

リスタート付きのGMRES法であるGMRES(k)法は，リスタート周期の取り方によって残差ベクトルのノルムの収束に影響を与えるため，
問題によってリスタート周期を適当に選ぶことが重要である．
GMRES(k)法のリスタート周期を動的に変化させる方法の一つに
Sosonkinaによって提案されたAdaptive GMRES(k)法があるが，リスタート周期を増やす処置しかないために問題によっては計算時間が必要以上にかかり適当でない．そこで本稿では，Adaptive GMRES(k)法を基本算法とし，リスタート周期を減らす過程を加えた算法を提案する．

Adaptive BiCGStab(ℓ) Algorithm with varying ℓ

Takashi Nodera, Kentaro Moriya

International Journal of Applied Science and Computations 7 ( ２ ) 87-95 2000.08

Research paper (scientific journal), Joint Work, Accepted

　View Summary

BiCGStab(ℓ) algorithm is one of iterative methods to solve large and sparse nonsymmetric linear systems of equations. It stabilizes the residual norm of BiCG (bi-conjugate gradient) algorithm by adapting ℓ degree MR (minimal residual) polynomial. When the degree of MR polynomial ℓ
becomes larger, the convergence of residual norm will be better.　However, the computational cost will be increased.
Sleijpen and van der Vorst proposed the BiCGStab(ℓ) algorithm with varying ℓ, when a breakdown of the algorithm occurs. But conventional BiCGStab(ℓ) algorithm often costs effective rather than their algorithm.
In this paper, it is both of when the norm of residual stagnates and the breakdown　is likely to occur, the BiCGStab($ell$) algorithm for varying ℓin adaptation is proposed. At last, this algorithm is implemented on the　distributed memory machine Fujitsu AP3000 and the numerical examples are given.

DGMRES(m,k) method with sparse approximate iverse preconditioning for solving nonsymmetric linear systems on Origin 2000

Takashi Nodera, Fuminori Ohsawa

World CSCC Conference (World Scientific and Engineering Society)     77-83 2000.07

Research paper (conference, symposium, etc.), Joint Work, Accepted

　View Summary

DQGMRES(k) method for solving nonsymmetric linear system
of equation is generally used with truncated procedure to reduce storage requirements and orthogonalization costs.
However, the truncated version sometimes slows down the convergence of algorithm in order to use incomplete orthogonalization. By using the restart technique, we proposethe DQGMRES(m,k) method which improves the convergence of residual norm. At last, the results of numerical experiments show that DQGMRES(m,k) method with an approximate inverse preconditioning gives a more robust algorithm than the other schemes.

左前処理行列を適応的に決定するGMRES(m)法の有効性について

Hiroo Suzuki, Takashi Nodera

情処研報 (情報処理学会HPC研究会)  2000 ( 57 ) 51-56 2000.05

Research paper (conference, symposium, etc.), Joint Work

　View Summary

大型で疎な非対称正則行列を係数とする連立1次方程式の反復解法の1つとして，GMRES(m)法がある．この算法はリスタートを行なうことによって，記憶容量や計算時間を軽減しているが，このことが原因で近似解を構成するために必要な固有ベクトルの情報を失い，算法の収束性に悪影響を及ぼすことがある．そこで，本稿では近似不変部分空間を用いて固有ベクトルの情報を付加するような左前処理行列を適応的に決定し，収束性を改善させる算法について述べ，並列計算機(Origin2000)での数値実験によりその有効性を検証する．

DQGMRES(m,k)法とその前処理

Fuminori Ohsawa, Takashi Nodera

情処研報 (情報処理学会HPC研究会)  1999 ( 103 ) 1-6 1999.12

Research paper (scientific journal), Single Work

　View Summary

連立１次方程式の近似解法の中で，GMRES法の打ち切り版として知られるDQGMRES(k)法は，記憶容量や計算コストを軽減する算法である．しかし，この打ち切り版は，不完全直交化によってしばしば算法の収束性を悪化させる．そこで，本稿ではリスタートを利用して，残差の収束性を改善させるDQGMRES(m,k)法を提案する．数値実験によれば，適切な前処理を行なうDQGMRES(m,k)法は，他の算法と比較して記憶容量と計算コストを減少させることができる．

自動リスタートによるGMRES(m)法の高速化

Takashi Nodera, Naoto Tsuno

京都大学数理解析研究所「偏微分方程式とその周辺」共同研究集会 (京都大学数理解析研究所)   1999.11

Joint Work

　View Summary

残差多項式のゼロ点を計算することによる自動リスタート型のGMRES(m)法の算法を提案し，並列計算機を用いた数値実験でその有効性を示した．

The Deflated-GMRES(m) method with switching the restart frequency Dynamically

Kentaro Moriya, Takashi Nodera

Linear Algebra and its Applications on Riken Symposium (The Institute of Physical and Chemical Research)     50 1999.11

Research paper (conference, symposium, etc.), Joint Work

　View Summary

In this paper, we propose an adaptive procedure that combines DEFLATED-GMRES(m.k) algorithm and the determination of a restart frequency m automatically. It is shown that a new algorithm combining elements of both will
reduce the negative effects of the restarted procedure.
The numerical experiments are presented on three test problems by using MIMD parallel machine AP3000. From these numerical results, we show that the proposed algorithm
leads to faster convergence than the conventional
DEFLATED-GMRES(m,k) method.

リスタート周期を動的に変えるGMRES(k)法について

Mitsuru Habu, Takashi Nodera

情処研報 (情報処理学会HPC研究会)  1999 ( 81 ) 7-12 1999.10

Research paper (scientific journal), Single Work

　View Summary

リスタート付きのGMRES法であるGMRES(k)法は，リスタート周期の
取り方によって残差ベクトルのノルムの収束に影響を与えるため，
問題によってリスタート周期を適当に選ぶことが重要である．
GMRES(k)法のリスタート周期を動的に変化させる方法の一つに
Sosonkinaらによって提案されたAdaptive GMRES(k)法があるが，リスタート周期を増やす処置しかないために問題によっては計算時間が必要以上にかかり適当でない．そこで本稿では，Adaptive GMRES(k)法を基本算法とし，リスタート周期を減らす過程を加えた算法を提案する．

An Improvement of the Convergence of ORTHOMIN(k) Algorithm by using Adaptive Restarts

Takashi Nodera, Naoto Tsuno

Iterative Methods in Scientific Computation IV (IMACS)     99-108 1999.06

Research paper (conference, symposium, etc.), Joint Work, Accepted,  ISSN  1098-870X

　View Summary

The ORTHOMIN(k) method, a truncated version of
the GCR (generalized conjugate residual) method,
has been widely used for solving large and sparse
nonsymmetric linear systems of equations Ax=b.
In order to accelerate the convergence of the
ORTHOMIN(k) method, we usually use the
restarting technique. But, it is not so easy to find out the restarting timing of its algorithm.
In this paper, we will propose the adaptive restarted
procedure which will detect the restarting timing of
the ORTHOMIN(k) method automatically.

適応的にℓを変化させるBiCGStab(ℓ)法

Kentarou Moriya, Takashi Nodera

情報処理学会論文誌 40 ( 6 ) 2669-2678 1999.06

Research paper (scientific journal), Joint Work, Accepted

Parallelization of ILU decomposition for elliptic boundary value problem of PDE on AP3000

Moriya Kentaro, NODERA TAKASHI

Lecture Note on Computer Science (ISHPC'99)     344-353 1999.05

Research paper (conference, symposium, etc.), Single Work

　View Summary

偏微分方程式の境界値問題の離散化行列に対する前処理を
並列計算機AP3000上で効率よく実装する手法について述べた論文である.

早期リスタートによるGMRES(m)法の高速化

Naoto Tsuno, Takashi Nodera

情報処理学会論文誌 40 ( 4 ) 1760-1773 1999.04

Research paper (scientific journal), Joint Work, Accepted

　View Summary

Krylov部分空間法の一つの算法としてGMRES(m)法がある。GMRES(m)法は、リスタートを行うことで残差ノルムの収束を改善する算法である。しかし、従来、このリスタート時期を決定することはユーザが問題に応じて、適当に決定していた。本論文は、このリスタートを適応的に行う手法を、残差多項式のゼロ点を計算することで可能にしたものである。特に、GMRES(m)法の最適な収束がほぼ期待できることを理論的な概念で示し、さらに数値実験を通してその有効性を示したものである。14頁

適応的なリスタートを用いたORTHOMIN（ｋ）法

Naoto Tsuno, Takashi Nodera

情報処理学会論文誌 40 ( 3 ) 1350 -1353 1999.03

Research paper (scientific journal), Joint Work, Accepted

　View Summary

GCR法（一般共役残差法）の打ち切り版であるORTHOMIN(k)法は，大規模で疎な非対称行列を係数とする連立1次方程式$Ax=b$の
反復解法として広く利用されている．ORTHOMIN(k)法の収束を加速するためにはリスタート技法を用いるのだが，そのタイミングを
見つけるのは簡単なことではない．本稿では，ORTHOMIN(k)法の算法をリスタートするタイミングを自動的に決定する適応的なリスタート技法を提案する．最後に，これらの算法を分散メモリ型並列計算機AP3000に実装し，その数値実験の結果について述べる．

適応的なリスタートを用いたORTHOMIN(k)法

津野 直人， 野寺 隆

情報処理学会論文誌 40 ( 3 ) 1350-1353 1999

Research paper (scientific journal), Joint Work, Accepted

　View Summary

CGR法の打ち切り版であるORTHOMIN（ｋ）法は，大規模で疎な非対称行列を係数とする連立１次方程式の反復解法として広く利用されている．本論文は，収束を加速するリスタートのタイミングを自動的に決定する技法を提案したものである． 4 頁.

AP3000における不完全LU分解の並列化の一考察

Takashi Nodera, and Kentaro Moriya

月刊地球/東京大学地震研究所共同研究集会「大規模計算と並列計算」 (海洋出版株式会社/東京大学地震研究所)  20 ( 12 ) 773-777 1998.12

Research paper (scientific journal), Joint Work

　View Summary

不完全LU分解を前処理とする反復解法は、楕円型偏微分方程式の離散化から選られる連立１次方程式の有功な算法である.この前処理を非定常反復法とカップリングして、分散メモリ型の並列計算機への効果的な実装について、数値実験と共に述べたものである.

デフレーションを前処理とするGMRES(m)法

Kentarou Moriya, Takashi Nodera

京都大学数理解析研究所「数値計算における前処理」研究集会 (京都大学数理解析研究所)   ( 1084 ) 72－86 1998.11

Research paper (bulletin of university, research institution), Joint Work

　View Summary

GMRES(m)法は，非対称で大型の係数行列を持つ連立1次方程式の反復解法の一つである．しかし，反復の途中でのリスタートによって，近似解を構成するための固有ベクトルの情報が欠落し，精度のよい解が構成できないことがある．本稿では，固有ベクトルの情報を付加する３つのGMRES(m)法について考察し，それらの算法の性能を分散メモリー型の並列計算機AP3000を使って評価する．

Deflation を用いたGMRES(m)法の収束性について

Hideaki Takashino, Kentaro Moriya, Takashi Nodera

情処研報 (情報処理学会HPC研究会)  1998 ( 93 ) 31-36 1998.10

Research paper (conference, symposium, etc.), Joint Work

　View Summary

GMRES(m)法は非対称行列系の反復解法としてよく用いられる算法であるが，リスタート時に近似解を構成するための固有ベクトルの情報を欠落させることがある．そこで，リスタートを行う前の固有ベクトルの情報を次の反復に反映させる算法を提案し，数値実験によりその算法の有効性について述べる．

Parallelization of incomplete LU decomposition with regards to 2 and 3 dimension problems on AP3000

Kentaro Moriya, Takashi Nodera

Proceedings of the 8th International Parallel Computing Workshop (School of Computing, National University of Singapore, Fujitsu Computers(Singapore) Pte Ltd)     P1-O-1--6 1998.09

Research paper (conference, symposium, etc.), Single Work

　View Summary

We propose the algorithm that decreases the communication
overhead on the block divide method and the method that determines the appropriate block number. We have implemented BiCGStab(ℓ) method with an ILU preconditioner based on our approach on the distributed memory parallel computer AP3000. We also analyze the performance of parallelism in the operation of ILU preconditioner throughout the numerical experiments.