A new preconditions for solving linear systems with symmetric Z-matrices

Abstract

There are many preconditioners for linear systems, for example, P = I + Smax developed by Kotakemori in [9] and its extension P˜ developed by Arenas & Yong in [1]. These preconditioners were built to speed up the convergence of the method when solving it. Symmetry is a useful property to preserve when applying a preconditioner. Preserving symmetry is advantageous since there are known methods that ensure convergence if the coefficient matrix is symmetric, among other things. Due to this fact, preconditioners that improve the convergence of the method at the same time that keeps symmetry are interesting and useful. This thesis introduces a new preconditioner, named PSY M, that preserves symmetricity of the coeficient matrix and improves the convergence of the Symmetric Gauss-Seidel method when applied. This new preconditioner was based on the one proposed by Arenas & Yong in [1] using the idea proposed by Kotakemori in [9]. This one is to turn the largest entry (in terms of absolute value) above the main diagonal, by row, into zero when the preconditioner is applied. By applying the new preconditioner, a clear reduction on the number of iterations until convergence and the elapsed time in the Symmetric Gauss-Seidel method is observed. In addition, a reduction of the condition number of the coefficient matrix is noticed. Even though this method is not as general as the one proposed by Arenas & Yong ([1]) or Kotakemori ([9]) when comparing them by considering the coefficient matrix as a symmetric one, the new method shows an improvement. On the other hand, other preconditioners, with the exception of, P˜, are not pose as iterative, the preconditioner proposed for this thesis, PSY M is. The preconditioner P˜ if applied iteratively, transforms the matrix into a lower triangular matrix; meanwhile, PSY M improves this. By applying the preconditioner PSY M iteratively, the matrix turns into a diagonal matrix.

Existen muchos precondicionadores para sistemas lineales, por ejemplo, P = I + Smax desarrollado por Kotakemori en [9] y su extensi´on P˜ desarrollada por Arenas & Yong en [1]. Estos precondicionadores fueron construidos para acelerar la convergencia del método al resolverlo. Es útil preservar la simetría cuando se aplica un precondicionador. Preservar la simetría es ventajoso ya que existen métodos que aseguran la convergencia si la matriz coeficiente es simétrica, entre otras cosas. Dado este hecho, precondicionadores que mejoran la convergencia del método al mismo tiempo que mantienen la simetría son interesantes y útiles. Esta tesis introduce un nuevo precondicionador, llamado PSY M , que preserva la simetría de la matriz coeficiente y mejora la convergencia del método Gauss-Seidel Simétrico. Este nuevo precondicionador fue basado en el propuesto por Arenas & Yong in [1] utilizando la idea propuesta por Kotakemori en [9]. Esta es volver la entrada más grande (en términos de valor absoluto) sobre la diagonal principal, por fila, en cero cuando se aplica el precondicionador. Aplicando el nuevo precondicionador, se observa una clara reducción en el número de iteraciones hasta la convergencia así como del tiempo de ejecución del método Gauss-Seidel Sim´etrico. En adición, se puede ver una reducción en el número de condicionamiento de la matriz coeficiente. Aunque este método no es tan general como los propuestos por Arenas & Yong ([1]) ´o Kotakemori ([9]), cuando se comparan estos considerando la matriz coeficiente como una simétrica, el nuevo método muestra una mejora. Por otro lado, otros precondicionadores, con la excepción de, P˜, no se plantean como iterativos, el precondicionador propuesto para ´esta tesis, PSY M, lo es. Si el precondicionador P˜ es aplicado iterativamente, transforma la matriz en una triangular inferior; PSY M mejora esto. Aplicando el precondicionador PSY M iterativamente, la matriz se convierte en una matriz diagonal.