論文

We have proposed an adaptive procedure for determining the optimal block-size for the Block Gram-Schmidt orthogonalization, which is a process for computing the QR factorization of matrix X.Accurate block-size is different for each numerous problem. In this paper, we have explored two new schemes for searching and finding accurate block-size under one execution of the QR factorization. Some numerical experiments will be used to illustrate the effectiveness of the proposed algorithm.

近年，第一種Fredholm積分方程式の離散化から導かれる連立$1$次方程式の近似解法としてGMRES法が注目を集めている．この連立1次方程式は離散型線形悪条件問題に分類され，悪条件問題としての困難な性質を持つため，克服すべき点は多い．今回提案する反復終了条件は，悪条件問題に対する古典的な手法の1つであるTikhonov正則化に基づく値を利用したものである．通常，GMRES法の反復終了条件には，相対残差ノルムを利用することが多い．しかし，離散型線形悪条件問題に対して用いる場合には，適切な反復終了条件として働かないため，他の基準が必要となる．そこで，適当なタイミングで反復終了を可能とするSimplified Tikhonov値を GMRES法の新たな反復終了条件として提案する．

downdating を含む最小二乗解を求める問題においても，Gram-Schmidt法は有用とされている．block Gram-Schmidt法は，$Q$のデータを使う回数を減らしキャッシュメモリを効率的に使用することにより，直交化をより効率的に行うことができる．これによって，block downdating のQR分解をより高速に求めることができる．block Gram-Schmidt法を用いたblock downdating に対する手法を提案し，数値実験でその有用性を示す．

GMRES法は，大規模な線形問題$Ax=b$に対するKrylov部分空間を用いた近似解法として使われる．GMRES法の収束は，固有値分布に大きく依存し，特に係数行列$Aには小さな固有値があるとき収束が遅くなることが知られている．Morganは，この欠点を改善するために，デフレーションを用いてDeflated GMRES($m,k$)法を提案した．本論文ではこの手法に前処理を加える手法を提案し，偏微分方程式の境界値問題を離散化することにより得られた線形問題に対して数値実験を行い，提案手法の有効性について述べる．

GMRES法は，大規模な線形問題$Ax=b$に対するKrylov部分空間を用いた近似解法として使われる．GMRES法の収束は，固有値分布に大きく依存し，特に係数行列$Aには小さな固有値があるとき収束が遅くなることが知られている．Morganは，この欠点を改善するために，デフレーションを用いてDeflated GMRES($m,k$)法を提案した．本論文ではこの手法に前処理を加える手法を提案し，偏微分方程式の境界値問題を離散化することにより得られた線形問題に対して数値実験を行い，提案手法の有効性について述べる．

In this paper, we are presenting a proposal for new modified algorithms for RRGMRES and AGMRES. It is known that RRGMRES and AGMRES are viable methods for solving linear discrete ill-posed problems. In this paper we have focused on the residual norm and have come-up with two improvements where successive updates and the stabilization of decreases for the residual norm improve performance respectively. Our numerical experiments confirm that our improved algorithms are effective for linear discrete ill-posed problems.

Tsuno and Nodera proposed a new variant of the GMRES(m) algorithm. Their algorithm is referred to as the GMRES(mmax) algorithm and performs the restart process adaptively, considering the distribution of the zeros of the residual polynomial. However, unless the zeros of the residual polynomial are distributed uniformly, mmax is always chosen and their algorithm becomes almost the same as the GMRES(m) algorithm with m=mmax. In this paper, we include a convergence test for the residual norm in the GMRES(mmax) algorithm and propose a new restarting technique based on two criteria. Even if the distribution of zeros does not become uniform, the restart can be performed by using the convergence test of the residual norm. Numerical examples simulated on a Compaq Beowulf computer demonstrate that the proposed technique accelerates the convergence of the GMRES(mmax) algorithm.

The Sherman–Morrison formula is one scheme for computing the approximate inverse preconditioner of a large linear system of equations. However, parallelizing a preconditioning approach is not straightforward as it is necessary to include a sequential process in the matrix factorization. In this paper, we propose a formula that improves the performance of the Sherman–Morrison preconditioner by partially parallelizing the matrix factorization. This study shows that our parallel technique implemented on a PC cluster system of eight processing elements significantly reduces the computational time for the matrix factorization compared with the time taken by a single processor. Our study has also verified that the Sherman–Morrison preconditioner performs better than ILU or MR preconditioners.

The GMRES method is an iterative method that provides better solutions when dealing with large linear systems of equations with a non-symmetric coefficient matrix. The GMRES method generates a Krylov subspace for the solution, and the augmented GMRES method allows augmentation of the Krylov subspaces by a user supplied subspace which represents certain known features of the desired solution. The augmented GMRES method performs well with suitable augmentation, but performs poorly with unsuitable augmentation. The adaptive augmented GMRES method automatically selects a suitable subspace from a set of candidates supplied by the user. This study shows that this method maintains the performance level of augmented GMRES and lightens the burden it puts on its users. Numerical experiments compare robustness as well as the efficiency of various heuristic strategies.