Numerical Analysis Seminars: Multigrid methods for matrices with structure and applications in image processing
8 November 2002 14:00 in CM105
"Multigrid methods are among the fastest algorithms for the solution of linear systems of equations Ax=b. For many problems the computational efforts for the multigrid solution of the linear system are of the same complexity as the multiplication of a vector with the matrix A. This talk deals with multigrid algorithms for structured linear systems. Particular focus is put on Toeplitz matrices, i.e. matrices with entries constant along diagonals. For the case of Toeplitz systems generated by nonnegative functions with a finite number of zeros of finite order new multigrid algorithms are proposed and efficiently implemented. It is pointed out why these algorithms are computationally superior to existing approaches.
Imaging applications are the most important practical source of Toeplitz systems: I will focus on Fredholm integral equations of the first kind arising from image deblurring. For the resulting discretization matrices a multigrid algorithm employing a natural coarse grid operator is implemented which improves on an existing approach by R.Chan, T.Chan and J.Wan. Finally, it will be explained how the new method can be viewed in the context of established multigrid approaches for Fredholm integral equations of the second kind. "
Contact David.Bourne@durham.ac.uk for more information