The block WZ factorization. (English) Zbl 1377.65036

Bylina, Beata

J. Comput. Appl. Math. 331, 119-132 (2018).

Summary: In the paper the author presents a novel kind of the WZ factorization algorithm, namely a block WZ factorization algorithm. The aim of this new algorithm is to utilize the computational power of contemporary computers with hierarchical memory. In the paper, some properties of the matrix Z are given and analyzed. Next, a version of the block WZ factorization is presented. The author shows that such a block WZ factorization exists for strictly diagonally dominant matrices. The computational cost of this block algorithm is presented. The time and the accuracy of proposed block WZ factorization algorithm for random dense square diagonally dominant matrices are reported. The block algorithm turned out to be faster even up to 300 times than the original WZ factorization.

MSC:

65F05	Direct numerical methods for linear systems and matrix inversion
15A23	Factorization of matrices

Keywords:

WZ factorization; block algorithm; solution of linear systems; quadrant interlocking factorization; memory hierarchy; strictly diagonally dominant matrices

Software:

LAPACK; Matlab

References:

[1]	Evans, D. J.; Hatzopoulos, M., The parallel solution of linear system, Int. J. Comput. Math., 7, 227-238, (1979) · Zbl 0442.65019
[2]	Flynn, M. J., Some computer organizations and their effectiveness, IEEE Trans. Comput., C-21, September, 948-960, (1972) · Zbl 0241.68020
[3]	Chandra Sekhara Rao, S., Existence and uniqueness of WZ factorization, Parallel Comput., 23, 1129-1139, (1997) · Zbl 0898.65012
[4]	Garcia, I.; Merelo, J. J.; Bruguera, J. D.; Zapata, E. L., Parallel quadrant interlocking factorization on hypercube computers, Parallel Comput., 15, 87-100, (1990) · Zbl 0707.65012
[5]	Yalamov, P.; Evans, D. J., The WZ matrix factorization method, Parallel Comput., 21, 1111-1120, (1995) · Zbl 0875.68775
[6]	Evans, D. J.; Barulli, M., BSP linear solver for dense matrices, Parallel Comput., 24, 777-795, (1998) · Zbl 0909.68013
[7]	Bylina, B.; Bylina, J., (Incomplete WZ Factorization As an Alternative Method of Preconditioning for Solving Markov Chains, Lecture Notes in Computer Science, vol. 4967, (2008), Springer-Verlag Berlin Heidelberg), 99-107
[8]	Bylina, B.; Bylina, J., Influence of preconditioning and blocking on accuracy in solving Markovian models, Int. J. Appl. Math. Comput. Sci., 19, 2, 207-217, (2009) · Zbl 1170.65022
[9]	Bylina, B.; Bylina, J., (The Vectorized and Parallelized Solving of Markovian Models for Optical Networks, Lecture Notes in Computer Science, vol. 3037, (2004), Springer-Verlag Berlin Heidelberg), 578-581 · Zbl 1081.68549
[10]	Chawla, M. M.; Khazal, R. R., A new WZ factorization for parallel solution of tridiagonal systems, Int. J. Comput. Math., 80, 1, 123-131, (2003) · Zbl 1035.65028
[11]	Demmel, J. W.; Higham, N. J.; Schreiber, R. S., Block LU factorization, Numer. Linear Algebra Appl., 2, 173-190, (1995) · Zbl 0834.65010
[12]	Schur, I., Über potenzreihen, die im innern des einheitskreises beschränkt sind, J. Reine Angew. Math., 147, 205-232, (1917) · JFM 46.0475.01
[13]	Zhang, F., The Schur Complement and Its Applications, (2005), Springer · Zbl 1075.15002
[14]	MATLAB, The Language of Technical Computing, http://www.mathworks.com/products/matlab/.
[15]	Anderson, E.; Bai, Z.; Bischof, C.; Blackford, S.; Demmel, J.; Dongarra, J.; Du Croz, J.; Greenbaum, A.; Hammarling, A. S.; McKenney, A.; Sorensen, D., LAPACK Users’ Guide, (1999), Society for Industrial and Applied Mathematics Philadelphia, PA, (paperback) · Zbl 0934.65030