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 thesis 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 nonnegative generating 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. For matrices arising from image deblurring 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, the work takes a look at the problem of high-resolution image reconstruction with multisensors. For the arising sparse linear systems a new method of optimal computational complexity is proposed, analyzed and integrated into a powerful software package.
«
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 thesis 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 nonnegative generating functions...
»
Translated abstract:
Mehrgittermethoden gehören zu den schnellsten Algorithmen für die Lösung eines linearen Gleichungssystems Ax=b. Für viele Probleme ist der Aufwand für die Mehrgitterlösung des linearen Gleichungssystems von der gleichen Komplexität wie die Multiplikation eines Vektors mit der Matrix A. Die vorliegende Arbeit untersucht Mehrgitteralgorithmen für strukturierte Gleichungssysteme. Ein besonderer Schwerpunkt liegt dabei auf Toeplitz-Matrizen, das sind Matrizen mit konstanten Einträgen entlang aller Diagonalen. Für den Fall nichtnegativer generierender Funktionen mit endlich vielen Nullstellen von endlicher Ordnung werden neue Mehrigitteralgorithmen vorgeschlagen und effizient implementiert. Es wird dargelegt, warum diese Algorithmen existierenden Ansätzen überlegen sind. Bildverarbeitungsanwendungen sind in der Praxis die bedeutendste Quelle für Toeplitz-Systeme. Für Matrizen, die aus der Bildentzerrung stammen, wird ein Mehrgitteralgorithmus mit einem natürlichen Grobgitteroperator implementiert, welcher einen existierenden Ansatz von R.Chan, T.Chan und J.Wan verbessert. Schließlich wirft die Arbeit einen Blick auf das Problem der hochauflösenden Bildrekonstruktion mit Multisensoren. Für die auftretenden dünnbesetzten linearen Gleichungssysteme wird ein neues Verfahren von optimaler Komplexität vorgeschlagen, analysiert und in ein leistungsfähiges Softwarepaket integriert.
«
Mehrgittermethoden gehören zu den schnellsten Algorithmen für die Lösung eines linearen Gleichungssystems Ax=b. Für viele Probleme ist der Aufwand für die Mehrgitterlösung des linearen Gleichungssystems von der gleichen Komplexität wie die Multiplikation eines Vektors mit der Matrix A. Die vorliegende Arbeit untersucht Mehrgitteralgorithmen für strukturierte Gleichungssysteme. Ein besonderer Schwerpunkt liegt dabei auf Toeplitz-Matrizen, das sind Matrizen mit konstanten Einträgen entlang aller D...
»