Fast textured algorithms and their parallel implementations.

摘要

A novel parallel processing approach, textured decomposition (TD) method, is proposed and investigated. The method attempts to utilize the inherent parallelism of classical iterative approach and cleverly exploits local behavior properties of systems, achieving an impressive convergence speed.;This dissertation first introduces the concept of textured decomposition of a linear system, analyzes convergence properties of the textured algorithms for a large class of banded linear systems. We have shown that for many banded linear algebraic systems arising from scientific and engineering applications, such as point diagonally dominant systems, block diagonally dominant systems, M-matrices and skew-symmetric tridiagonal systems, the textured algorithms converge and have a better convergence speed than the associated Jacobi algorithms. We have also shown that for any systems which possess certain local behavior properties, the convergence rate of the classical iterative algorithms such as Jacobi type algorithms can be improved by using the textured decomposition methods.;Applications of textured decomposition method to the numerical solution of partial differential equations (PDEs) are then examined. We have applied the textured decomposition methods, together with the recursion, reordering and preconditioning techniques, to the numerical solution of several important classes of PDEs, such as elliptic equations, parabolic equations and first order PDEs. We have shown that for one dimensional (1-D), 2-D and space-varying elliptic problems, the parallel time complexity of recursive multiplicative textured algorithms is ;Finally, the implementation of textured algorithms on some parallel computer architectures, such as mesh-connected arrays and hypercube networks, is discussed. We have shown that the multiplicative textured algorithms with any number of recursion levels need only local information exchange and they can be naturally implemented on mesh-connected arrays, and the recursive additive textured algorithms can be effectively mapped onto hypercube networks, though the algorithms need global communications to perform averagings of local solution estimates.