| The high-performance solution of sparse linear algebra equations is very important in solving many problems from science and engineering applications, including computational fluid, simulation and design of materials, data processing in oil exploitation and earthquake prediction, numerical forecast of weather, and numerical simulation of nuclear blast.The traditional methods are to solve the linear algebra equations directly, based on matrix factorization such as LU decomposition. With this kind of methods, the 'true' solution can be derived if there is no consideration of the round error. But when the condition number of the matrix is very large, the round error will be accumulated to collapse the true solution, that is, the method is unstable. What's more, when there is no structure with the non-zero pattern of the matrix, or its bandwidth is very large, the required memory will be beyond the available one and the time spent will be beyond our patience.Instead, there needs to store only the original coefficient matrix, some auxiliary matrices for the preconditioner and several vectors in the iteration methods. Further, the core of the iteration is the matrix-vector multiplication and the solution of the auxiliary equations corresponding to the preconditioner. If the solution of the auxiliaries spend not very much, the computational cost in each iteration step will be very cheap, due to the fact that the sparsity of the matrix can be exploited sufficiently.But the iterations may converge very slowly or even diverge. In general the convergence is related to the distribution of the eigenvalues of the coefficient matrix. For the Krylov subspace methods, which attract most attention in recent years, the smaller area the eigenvalues locate in, the higher convergent velocity there will be. The usage of preconditioned is to improve the distribution of the eigenvalues. The construction of efficient preconditioned is a hot spot of the study of iterations in these years.Besides the preconditioning techniques, there arc many other methods to turn the original matrix to a new one of better properties. Pre-symmetry is such a kind of technique. CG is stable and efficient, but it can only be used to symmetric matrices. If the matrix can be turned to be a symmetric one, the CG iteration can be used thereby.Based on the above considerations, there have mainly done the following studies in the paper:(1) For the incomplete Cholesky decomposition, there first derived an efficient implementation with the help of several integer vectors, and the computation of its modification is also in consideration. Second, there apply the drop strategy before a certain number of rows are computed at a time. Since the dropped elements are relatively smaller in module than the method that there compute only one row at a time, the new strategy will have clear improvements. Finally, when the decomposition is proceeding to a symmetric positive definite matrix, the pivot may be very small or even negative. There provided several methods to overcome this shortcoming.(2) For the block strictly diagonally dominant matrices, there proved the existence anduniqueness of the block LU decomposition and the existence of the incomplete version. For both block strictly diagonally dominant and block irreducible diagonally dominant matrices, there proved the convergence of some basic iterative methods, including block Jacobi. block Gauss-Seidel, block SOR and block SSOR ones. Consequently, there analyzed the distribution of eigenvalues of the preconditioned matrix if these basic iterations are used as preconditioners. Finally, there analyzed some approaches of turning a non-singular matrix to a block diagonally dominant one of appropriate block size. With the help of METIS, which is a software package in static graph partitioning, we construct a type of block Jacobi preconditioner. The numerical experiments show that the preconditioner is robust and efficient.(3) For the block tridiagonal matrices d...
|
PDF Full Text Request