Michela Redivo Zaglia (Università di Padova): Acceleration of Kaczmarz's method for solving linear systems

Academic or specialist Colloquium / Congress / Forum

The Method of Alternating Projections (MAP)
[R. Escalante, M. Raydan, {\it Alternating Projection Methods},
SIAM, Philadelphia, 2011] is an iterative procedure for finding the projection of a
point on the intersection of closed subspaces of an Hilbert space. The convergence
of this method is usually slow, and several methods for its acceleration have
already been proposed.

In this work, we consider a special MAP, namely Kaczmarz'
method for solving systems of linear equations
[S. Kaczmarz, Angen\""aherte Aufl\""osung von Systemen linearer Gleichungen,
Bull. Acad. Polon. Sci., A35 (1937), pp. 355--357. English translation:
Approximate solution of systems of linear equations,
Int. J. Control, 57 (1993), pp. 1269--1271].
The convergence of this method is discussed. After
giving its matrix formulation and its projection properties,
we consider several procedures for accelerating its convergence.
They are based on sequence transformations whose kernels contain
sequences of the same form as the sequence of vectors generated by
Kaczmarz' method. Acceleration can be achieved either directly,
that is without modifying the sequence obtained by the method (AK algorithm),
or by restarting it from the vector obtained by acceleration (RK algorithm).
Numerical examples show the effectiveness of both procedures.

This is a joint work with Claude Brezinski (University of Lille,

When? 26.11.2013 17:15
Where? PER 08 Phys 2.52
Chemin du Musée 3
1700 Fribourg
Contact Department of Mathematics