Premium
On the Acceleration of Kaczmarz Projection Algorithm
Author(s) -
Pomparău Ioana
Publication year - 2013
Publication title -
pamm
Language(s) - English
Resource type - Journals
ISSN - 1617-7061
DOI - 10.1002/pamm.201310205
Subject(s) - algorithm , convergence (economics) , acceleration , mathematics , matrix (chemical analysis) , projection (relational algebra) , hamming distance , cluster analysis , computer science , statistics , physics , materials science , classical mechanics , economics , composite material , economic growth
In the paper [1], a direct version of the classical Kaczmarz algorithm was proposed, which gives us in only one iteration a solution of an arbitrary consistent system of linear equations. Unfortunately, as any direct method applied to large sparse matrices, this algorithm is based on some modifications of the system matrix sparsity structure such that a big fill‐in appears. In order to overcome this difficulty, in the present paper we propose a modified version of this direct Kaczmarz algorithm in which the transformations applied to the system matrix try to conserve the initial sparsity structure. This transformations are done via clustering using Jaccard and Hamming distances. The modified Kaczmarz algorithm is no more a direct method, but we obtain an acceleration of convergence with respect to the classical Kaczmarz algorithm. Numerical experiments which ilustrate the efficiency of our algorithm are also presented. (© 2013 Wiley‐VCH Verlag GmbH & Co. KGaA, Weinheim)