A Review on Quadrant Interlocking Factorization: WZ and WH Factorization

Dlal Bashir; Hailiza Kamarulhaili; Olayiwola Babarinsa

doi:10.46481/jnsps.2023.1112

Authors

Dlal Bashir
[email protected]

School of Mathematical Sciences, Universiti Sains Malaysia, 11800 Pulau Pinang, Malaysia
Hailiza Kamarulhaili
School of Mathematical Sciences, Universiti Sains Malaysia, 11800 Pulau Pinang, Malaysia
Olayiwola Babarinsa
Department of Mathematics, Federal University Lokoja, Kogi State, Nigeria

Keywords:

Quadrant interlocking factorization,WZ factorization,WH factorization, LU factorization, Linear systems

Abstract

Quadrant Interlocking Factorization (QIF), an alternative to LU factorization, is suitable for factorizing invertible matrix A such that det(A) , 0. The QIF, with its application in parallel computing, is the most efficient matrix factorization technique yet underutilized. The two forms of QIF among others, which are not only similar in algorithm but also in computation, are WZ factorization and WH factorization yet differs in applications and properties. This review discusses both the old form of QIF, called WZ factorization, and the latest form of QIF, called WH factorization, with an example and open questions to further the studies between the two factorization techniques.

Dimensions

REFERENCES

F. Bornemann, Matrix Factorization, Springer (2018). DOI: https://doi.org/10.1007/978-3-319-74222-9_2

J. R. Bunch & J. E. Hopcroft, “Triangular factorization and inversion by fast matrix multiplication”, Mathematics of Computation 28 (1974) 231. DOI: https://doi.org/10.1090/S0025-5718-1974-0331751-8

K. Murota, “LU-decomposition of a matrix with entries of different kinds”, Linear Algebra and its Applications 49 (1983) 275. DOI: https://doi.org/10.1016/0024-3795(83)90109-X

A. Townsend & L. N. Trefethen, “Continuous analogues of matrix factorizations”, in Proceedings of Rotal Society A 471, (2015) 585. DOI: https://doi.org/10.1098/rspa.2014.0585

X. Wang, P. H. Jones & J. Zambreno, “A configurable architecture for sparse lu decomposition on matrices with arbitrary patterns”, ACM SIGARCH Computer Architecture News 43 (2016) 76. DOI: https://doi.org/10.1145/2927964.2927978

J. Dongarra, M. Faverge, H. Ltaief & P. Luszczek, “Achieving numerical accuracy and high performance using recursive tile LU factorization with partial pivoting”, Concurrency and Computation: Practice and Experience 26 (2014) 1408. DOI: https://doi.org/10.1002/cpe.3110

D. J. Evans & M. Hatzopoulos, “The parallel calculation of the eigenvalues of a real matrix”, Computers and Mathematics with Applications, 4 (1978) 211. http://dx.doi.org/http://dx.doi.org/10.1016/0898-1221(78)90032-9 DOI: https://doi.org/10.1016/0898-1221(78)90032-9

S. Rao, “Existence and uniqueness of wz factorization”, Parallel Comput. 23 (1997) 1129. DOI: https://doi.org/10.1016/S0167-8191(97)00042-2

B. Bylina & J. Bylina, “Incomplete wz factorization as an alternative method of preconditioning for solving markov chains”, International Conference on Parallel Processing and Applied Mathematics, Springer (2017) 99. DOI: https://doi.org/10.1007/978-3-540-68111-3_11

D. Evans & M. Hatzopoulos, “A parallel linear system solver”, Int. J. Comput. Math. 7 (1979) 227. DOI: https://doi.org/10.1080/00207167908803174

D. Evans, “The QIF singular value decomposition method”, Int. J. Comput. Math. 79 (2002) 637. DOI: https://doi.org/10.1080/00207160210957

P. Huang, A. MacKay & D. Teng, “A hardware/software codesign of wz factorization to improve time to solve matrices”, Canadian Conference on Electrical and Computer Engineering, IEEE, (2010) 1. DOI: https://doi.org/10.1109/CCECE.2010.5575119

B. Bylina & J. Bylina, ”The parallel tiled WZ factorization algorithm for multicore architectures”, Int. J. Appl. Math. Comput. Sci. 29(2019) 407. DOI: https://doi.org/10.2478/amcs-2019-0030

B. Bylina, ”Solving linear systems with vectorized WZ factorization”, Annales UMCS Informatica 1 (2003) 1.

G. Heinig & K. Rost, “Schur-type algorithms for the solution of Hermitian Toeplitz systems via factorization”, Springer (2005) 233. DOI: https://doi.org/10.1007/3-7643-7398-9_11

B. Bylina & J. Bylina, “Mixed precision iterative refinement techniques for the wz factorization”, IEEE Federated Conference on Computer Science and Information Systems (2013) 425.

O. Babarinsa, Z. M. S. Azfi, A. H. I. Mohd & K. Hailiza, “Optimized cramer’s rule in wz factorization and applications”, European Journal of Pure and Applied Mathematics 13 (2020) 1035. DOI: https://doi.org/10.29020/nybg.ejpam.v13i4.3818

M. Brunetti & A. Renato, “Old and new proofs of cramer’s rule”, Appl. Math. Sci. 8 (2014) 6689. DOI: https://doi.org/10.12988/ams.2014.49683

B. Bylina & J. Bylina, “The WZ factorization in matlab”, IEEE Federated Conference on Computer Science and Information Systems (2014) 561.

D. Levin & D. Evans, “The inversion of matrices by the double-bordering algorithm on mimd computers”, Parallel Comput. 17 (1991) 591. DOI: https://doi.org/10.1016/S0167-8191(05)80159-0

S. C. S. Rao & R. Kamra, “A stable parallel algorithm for diagonally dominant tridiagonal linear systems”, 22nd International Conference on High Performance Computing (2015) 95.

M. Kaps & M. Schlegl, “A short proof for the existence of the WZ factorisation”, Parallel Comput. 4 (1987) 229. DOI: https://doi.org/10.1016/0167-8191(87)90056-1

E. Golpar-Raboky, “A new approach for computing WZ factorization”, Appl. Appl. Math. 7 (2012) 571.

P. Yalamov & D. Evans, “The WZ matrix factorisation method”, Parallel Computing 21 (1995) 1111. DOI: https://doi.org/10.1016/0167-8191(94)00088-R

B. Bylina, “The inverse iteration with theWZ factorization used to the markovian models”, Annales UMCS Informatica AI 2 (2015) 15.

B. Bylina, “The block WZ factorization”, J. Comput. Appl. Math. 331 (2018) 119. DOI: https://doi.org/10.1016/j.cam.2017.10.004

B. Bylina & J. Bylina, “Influence of preconditioning and blocking on accuracy in solving markovian models”, Int. J. Appl. Math. Comput. Sci. 19 (2009) 207. DOI: https://doi.org/10.2478/v10006-009-0017-3

J. Bylina & B. Bylina, “Parallelizing nested loops on the intel xeon phi on the example of the dense wz factorization”, 2016 IEEE Federated Conference on Computer Science and Information Systems (2016) 655. DOI: https://doi.org/10.15439/2016F436

B. Bylina & J. Bylina, “GPU-accelerated wz factorization with the use of the cublas library”, IEEE Federated Conference on Computer Science and Information System (2012) 509.

D. Evans & G. Oksa, “Parallel solution of symmetric positive definite toeplitz systems”, Parallel Algorithms Appl. 12 (1997) 297. DOI: https://doi.org/10.1080/01495739708941427

O. Efremides, M. Bekakos & D. Evans, “Implementation of the generalized WZ factorization on a wavefront array processor”, Int. J. Comput. Math. 79 (2002) 807. DOI: https://doi.org/10.1080/00207160211299

K. Rhofi, M. Ameur & A. Radid, “Double power method iteration for parallel eigenvalue problem”, Int. J. Pure Appl. Math. 108 (2016) 945. DOI: https://doi.org/10.12732/ijpam.v108i4.19

B. Bylina, J. Bylina & M. Piekarz, “Influence of loop transformations on performance and energy consumption of the multithreded WZ factorization”, 17th IEEE Conference on Computer Science and Intelligence Systems (2022) 479. DOI: https://doi.org/10.15439/2022F251

A. Benaini & D. Laiymani, “Generalized WZ factorization on a reconfigurable machine”, Parallel Algorithms Appl. 3 (1994) 261. DOI: https://doi.org/10.1080/10637199408962542

D. Evans & R. Abdullah, “The parallel implicit elimination (pie) method for the solution of linear systems”, Parallel Algorithms Appl. 1 (1994) 153. DOI: https://doi.org/10.1080/10637199408915461

E. Golpar-Raboky & E. Babolian, “On the WZ factorization of the real and integer matrices”, Iranian Journal of Mathematical Sciences and Informatics 17 (2022) 71. DOI: https://doi.org/10.52547/ijmsi.17.1.71

D. J. Tylavsky, “Quadrant interlocking factorization: a form of block LU factorization”, IEEE Proceedings (1986) 232. DOI: https://doi.org/10.1109/PROC.1986.13446

I. Garcia, J. Merelo, J. D. Bruguera & E. L. “Zapata, Parallel quadrant interlocking factorization on hypercube computers”, Parallel computing 15 (1990) 87. DOI: https://doi.org/10.1016/0167-8191(90)90033-6

R. Asenjo & M. Ujaldon & E. Zapata, “Parallel WZ factorization on mesh multiprocessors”, Microprocessing and Microprogramming 38 (1993) 319. DOI: https://doi.org/10.1016/0165-6074(93)90161-D

G. Heinig & K. Rost, “Fast algorithms for toeplitz and hankel matrices”, Linear Algebra Appl. 435 (2011) 1. DOI: https://doi.org/10.1016/j.laa.2010.12.001

B. Bylina & J. Bylina, “Analysis and comparison of reordering for two factorization methods (LU and WZ) for sparse matrices”, International Conference on Computational Science (2008) 983. DOI: https://doi.org/10.1007/978-3-540-69384-0_103

D. Ahmed & N. Askar, “Parallelize and analysis LU factorization and quadrant interlocking factorization algorithm in openmp”, Journal of Duhok University (2018) 46. DOI: https://doi.org/10.26682/sjuod.2018.20.1.5

B. Bylina & J. Bylina, “OpenMP thread affinity for matrix factorization on multicore systems”, IEEE Federated Conference on Computer Science and Information Systems (2017) 489. DOI: https://doi.org/10.15439/2017F231

C. Demeure, “Bowtie factors of toeplitz matrices by means of split algorithms”, IEEE Transactions on Acoustics, Speech, and Signal Processing 37 (1989) 1601. DOI: https://doi.org/10.1109/29.35401

O. Babarinsa & H. Kamarulhaili, “Quadrant interlocking factorization of hourglass matrix”, AIP Conference Proceedings 030009, 2018, 1.

O. Babarinsa, M. Arif & H. Kamarulhaili, “Potential applications of hourglass matrix and its quadrant interlocking factorization”, ASM Science Journal 12 (2019) 72. DOI: https://doi.org/10.1063/1.5041653

O. Babarinsa, O. Ihinkalu, V. Cyril-Okeme, H. Kamarulhaili, A. Mandangan, A. Z. M. Sofi & A. B. Disu, “Application of hourglass matrix in goldreich-goldwasser-halevi encryption scheme”, Journal of the Nigerian Society of Physical Sciences (2022) 874. DOI: https://doi.org/10.46481/jnsps.2022.874

O. Babarinsa, H. Kamarulhaili, “Mixed hourglass graph”, AIP Conference Proceedings 2184 (2019).

S. Arumugam, A. Brandstadt, T. Nishizeki&K. Thulasiraman, Handbook of graph theory, combinatorial optimization, and algorithms, Chapman and Hall/CRC (2016).

O. Babarinsa, “Graph theory: A lost component for development in Nigeria”, Journal of the Nigerian Society of Physical Sciences 4 (2022) 1. http://dx.doi.org/DOI:10.46481/jnsps.2022.844 DOI: https://doi.org/10.46481/jnsps.2022.844

K. Guo & B. Mohar, “Hermitian adjacency matrix of digraphs and mixed graphs”, Journal of Graph Theory 85 (2015) 217. DOI: https://doi.org/10.1002/jgt.22057

R. Ponraj, S. S. Narayanan & A. Ramasamy, “Total mean cordiality of umbrella, butterfly and dumbbell graphs”, Jordan J. Math. and Stat.(JJMS) 8 (2015) 59. DOI: https://doi.org/10.1515/tmj-2015-0009

S. Alikhani, J. I. Brown & S. Jahari, “On the domination polynomials of friendship graphs”, Filomat 30 (2016) 169. DOI: https://doi.org/10.2298/FIL1601169A

M. Liu, Y. Zhu, H. Shan & K. C. Das, “The spectral characterization of butterfly-like graphs”, Linear Algebra and its Applications 513 (2017) 55. DOI: https://doi.org/10.1016/j.laa.2016.10.003

O. Babarinsa & H. Kamarulhaili, Mixed energy of a mixed hourglass graph, Communications in Mathematics and Applications 10 (2019) 45. http://dx.doi.org/10.26713/cma.v10i1.1143 DOI: https://doi.org/10.1063/1.5136357