Enhancement of the Kaczmarz algorithm with projection adjustment
- PDF / 2,293,496 Bytes
- 24 Pages / 439.642 x 666.49 pts Page_size
- 90 Downloads / 168 Views
Enhancement of the Kaczmarz algorithm with projection adjustment Chuan Lin1
· Gabor T. Herman2 · Marcelo V. W. Zibetti3
Received: 17 May 2019 / Accepted: 21 October 2019 / © Springer Science+Business Media, LLC, part of Springer Nature 2019
Abstract Projection adjustment is a technique that improves the rate of convergence, as measured by the number of iterations needed to achieve a given level of performance, of the Kaczmarz algorithm (KA) for iteratively solving a system of consistent linear equations, however at the cost of requiring additional time per iteration and increased storage. This hinders the applicability of the previously published Kaczmarz algorithm with projection adjustment (KAPA) to large-scale problems. An enhancement EKAPA of KAPA that uses projection adjustment only for a small subset of the equations is proposed for significantly reducing the time and storage requirements. An analysis of the behavior of EKAPA is provided. An illustration is given to show that EKAPA using a small subset of the equations for projection adjustment can achieve a speed-up over KA similar to that of KAPA in terms of the number of iterations, but requires much less computer time and storage; hence, it is more suitable for large-scale problems. Keywords Kaczmarz algorithm · Linear equations · Numerical linear algebra · Performance of algorithms Mathematics Subject Classification (2010) 15A06 · 65F10 · 65Y20
1 Introduction In the notation adopted here, a linear system of equations is expressed as Rx = y,
A preliminary report on generalizing KAPA was submitted as an abstract by Chuan Lin, Anyong Qing, and Jiefeng Zang to the 2016 Progress in Electromagnetic Research Symposium. Chuan Lin
lin [email protected]
Extended author information available on the last page of the article.
(1)
Numerical Algorithms
where x is a J -dimensional vector that is unknown and need to be found from (1) and y is an L-dimensional vector. For 1 ≤ l ≤ L, we use yl to denote the lth component of y. R is an L × J matrix. For 1 ≤ l ≤ L, we use rl to denote the J -dimensional vector that is the transpose of the lth row of R and we assume that the norm rl = 0. Using ·, · for inner product, the lth equation of the linear system (1) is expressed as rl , x = yl .
(2)
We assume consistency; so there is a J -dimensional vector x∗ such that, for 1 ≤ l ≤ L, rl , x∗ = yl . (3) Solving linear systems of equations is basic mathematics, various direct and iterative methods can be used for this purpose [1, 35]. If the dimensions of the system matrix R are huge, as in tomographic image reconstruction [17], it is not practical to try to use the inverse of the matrix R, and iterative methods are applied in practice. Many iterative methods have been developed to solve these problems [25]. Row projection or row action methods are one class of the most frequently used iterative methods for solving large linear system of equations and have been widely studied [7, 8, 31]. The main feature of row action methods is that they make no change to the
Data Loading...
