Text only print
Full screen print
Numerical Analysis Seminar
Seminar information archive ～04/19｜Next seminar｜Future seminars 04/20～
| Date, time & place | Tuesday 16:30 - 18:00 002Room #002 (Graduate School of Math. Sci. Bldg.) |
|---|---|
| Organizer(s) | Norikazu Saito, Takahito Kashiwabara |
2016/05/23
16:30-18:00 Room #056 (Graduate School of Math. Sci. Bldg.)
Keiichi Morikuni (University of Tsukuba)
Inner-iteration preconditioning for least squares problems and its applications (日本語)
Keiichi Morikuni (University of Tsukuba)
Inner-iteration preconditioning for least squares problems and its applications (日本語)
[ Abstract ]
We discuss inner-iteration preconditioning for Krylov subspace methods for solving large-scale linear least squares problems. The preconditioning uses several steps of stationary iterative methods, and is efficient when the successive overrelaxation (SOR) method for the normal equations is employed. The SOR inner-iteration left/right-preconditioned generalized minimal residual (BA/AB-GMRES) methods determine a least squares solution/the minimum-norm solution of linear systems of equations without breakdown even in the rank-deficient case. The inner-iteration preconditioning requires less memory than incomplete matrix factorization-type one, and is effective for ill-conditioned and/or rank-deficient least squares problems.
We present applications of inner-iteration preconditioning to solutions of (1) general least squares problems, which is to find a least squares solution whose Euclidean norm is minimum; (2) linear systems of equations which arise in an interior-point method for solving linear programming problems. In (1), we focus on a two-step procedure for the solution of general least squares problems; the first step is to determine a least squares solution and the second step is to determine the minimum-norm solution to a linear system of equation. The solution of each step can be done by using the inner-iteration preconditioned GMRES methods. Numerical experiments show that the SOR inner-iteration preconditioned GMRES methods are more efficient than previous methods for some problems. In (2), the linear systems of equations at each interior-point step become ill-conditioned in the late phase of the interior-point iterations. To solve the linear systems of equation robustly, the inner-iteration preconditioning applies. We present efficient techniques to apply the inner-iteration preconditioning to the linear systems of equations. Numerical experiments on benchmark problems show that the inner-iteration preconditioning is robust compared to previous methods. (2) is joint work with Yiran Cui (University College London), Takashi Tsuchiya (National Graduate Institute for Policy Studies) , and Ken Hayami (National Institute of Informatics and SOKENDAI).
We discuss inner-iteration preconditioning for Krylov subspace methods for solving large-scale linear least squares problems. The preconditioning uses several steps of stationary iterative methods, and is efficient when the successive overrelaxation (SOR) method for the normal equations is employed. The SOR inner-iteration left/right-preconditioned generalized minimal residual (BA/AB-GMRES) methods determine a least squares solution/the minimum-norm solution of linear systems of equations without breakdown even in the rank-deficient case. The inner-iteration preconditioning requires less memory than incomplete matrix factorization-type one, and is effective for ill-conditioned and/or rank-deficient least squares problems.
We present applications of inner-iteration preconditioning to solutions of (1) general least squares problems, which is to find a least squares solution whose Euclidean norm is minimum; (2) linear systems of equations which arise in an interior-point method for solving linear programming problems. In (1), we focus on a two-step procedure for the solution of general least squares problems; the first step is to determine a least squares solution and the second step is to determine the minimum-norm solution to a linear system of equation. The solution of each step can be done by using the inner-iteration preconditioned GMRES methods. Numerical experiments show that the SOR inner-iteration preconditioned GMRES methods are more efficient than previous methods for some problems. In (2), the linear systems of equations at each interior-point step become ill-conditioned in the late phase of the interior-point iterations. To solve the linear systems of equation robustly, the inner-iteration preconditioning applies. We present efficient techniques to apply the inner-iteration preconditioning to the linear systems of equations. Numerical experiments on benchmark problems show that the inner-iteration preconditioning is robust compared to previous methods. (2) is joint work with Yiran Cui (University College London), Takashi Tsuchiya (National Graduate Institute for Policy Studies) , and Ken Hayami (National Institute of Informatics and SOKENDAI).
