A Class of Generalized Approximate Inverse Solvers for Unsymmetric Linear Systems of Irregular Structure Based on Adaptive Algorithmic Modelling for Solving Complex Computational Problems in Three Space Dimensions
A class of general inverse matrix
techniques based on adaptive algorithmic modelling methodologies is derived
yielding iterative methods for solving unsymmetric linear systems of irregular
structure arising in complex computational problems in three space dimensions.
The proposed class of approximate inverse is chosen as the basis to yield
systems on which classic and preconditioned iterative methods are explicitly
applied. Optimized versions of the proposed approximate inverse are presented
using special storage (k-sweep) techniques leading to economical forms of the
approximate inverses. Application of the adaptive algorithmic methodologies on
a characteristic nonlinear boundary value problem is discussed and numerical
results are given.
References
[1]
Guillaume, P., Huard, A. and Le Calvez, C. (2002) A Block Constant Approximate Inverse for Preconditioning Large Linear Systems. SIAM Journal on Matrix Analysis and Applications, 24, 822-851.
http://dx.doi.org/10.1137/S0895479802401515
[2]
He, B. and Teixeira, F.L. (2007) Differential Forms, Galerkin Duality, and Sparse Inverse Approximations in Finite Element Solutions of Maxwell Equations. IEEE Transactions on Antennas and Propagation, 55, 1359-1368.
http://dx.doi.org/10.1109/TAP.2007.895619
[3]
Helsing, J. (2006) Approximate Inverse Preconditioners for Some Large Dense Random Electrostatic Interaction Matrices. BIT Numerical Mathematics, 46, 307-323. http://dx.doi.org/10.1007/s10543-006-0057-0
[4]
Cerdan, J., Faraj, T., Malla, N., Marin, J. and Mas, J. (2010) Block Approximate Inverse Preconditioners for Sparse Nonsymmetric Linear Systems. Electronic Transactions on Numerical Analysis, 37, 23-40.
[5]
Cui, X. and Havami, K. (2009) Generalized Approximate Inverse Preconditioners for Least Squares Problems. Japan Journal of Industrial and Applied Mathematics, 26, 1-14. http://dx.doi.org/10.1007/BF03167543
[6]
Gravvanis, G.A., Filelis-Papadopoulos, C.K., Giannoutakis, K.M. and Lipitakis, E.A. (2013) A Note on Parallel Finite Difference Approximate Inverse Preconditioning on Multicore Systems Using POSIX Threads. International Journal of Computational Methods, 10, Article ID: 1350032. http://dx.doi.org/10.1142/S0219876213500321
[7]
Giannoutakis, K., Gravvanis, G., Clayton, B., Patil, A., Enright, T. and Morrison, J. (2007).Matching High Performance Approximate Inverse Preconditioning to Architectural Platforms. The Journal of Supercomputing, 42, 145-163.
http://dx.doi.org/10.1007/s11227-007-0129-1
[8]
Gravvanis, G.A., Epitropou, V.N. and Giannoutakis, K.M. (2007) On the Performance of Parallel Approximate Inverse Preconditioning Using Java Multithreading Techniques. Applied Mathematics and Computation, 190, 255-270.
http://dx.doi.org/10.1016/j.amc.2007.01.024
[9]
Ngo, C., Yashtini, M. and Zhang, H.C. (2015) An Alternating Direction Approximate Newton Algorithm for Ill-Conditioned Inverse Problems with Application to Parallel MRI. Journal of the Operations Research Society of China, 3, 139-162. http://dx.doi.org/10.1007/s40305-015-0078-y
[10]
Wang, H., Li, E. and Li, G. (2013) A Parallel Reanalysis Method Based on Approximate Inverse Matrix for Complex Engineering Problems. Journal of Mechanical Design, 135, Article ID: 081001. http://dx.doi.org/10.1115/1.4024368
[11]
Xu, S., Xue, W., Wang, K. and Lin, H. (2011) Generating Approximate Inverse Preconditioners for Sparse Matrices Using CUDA and GPGPU. Journal of Algorithms and Computational Technology, 5, 475-500.
http://dx.doi.org/10.1260/1748-3018.5.3.475
[12]
Alleon, G., Benzi, M. and Giraud, L. (1997) Sparse Approximate Inverse Preconditioning for Dense Linear Systems Arising in Computational Electromagnetics. Numerical Algorithms, 16. http://dx.doi.org/10.1023/A:1019170609950
[13]
Dubois, P.F., Greenbaum, A. and Rodrigue, G.H. (1979) Approximating the Inverse of a Matrix for Use in Iterative Algorithms on Vector Processors. Computing, 22, 257-268. http://dx.doi.org/10.1007/BF02243566
[14]
Grote, M.J. and Huckle, T. (1997) Parallel Preconditioning with Sparse Approximate Inverses. SIAM Journal on Scientific Computing, 18, 838-853. http://dx.doi.org/10.1137/S1064827594276552
[15]
Van der Vorst, H.A. (1989) High Performance Preconditioning. SIAM Journal on Scientific Computing, 10, 1174-1185. http://dx.doi.org/10.1137/0910071
[16]
Broker, O., Grote, J., Mayer, C. and Reusken, A. (2001) Robust Parallel Smoothing for Multigrid via Sparse Approximate Inverses. SIAM Journal on Scientific Computing, 23, 1396-1417. http://dx.doi.org/10.1137/S1064827500380623
[17]
Chow, E. (2000) A Priori Sparsity Patterns for Parallel Sparse Approximate Inverse Preconditioners. SIAM Journal on Scientific Computing, 21, 1804-1822. http://dx.doi.org/10.1137/S106482759833913X
[18]
Chow, E. (2001) Parallel Implementation and Practical Use of Sparse Approximate Inverse Preconditioners with a Priori Sparsity Patterns. International Journal of High Performance Computing Applications, 15, 56-74.
http://dx.doi.org/10.1177/109434200101500106
[19]
Kallischko, A. (2008) Modified Sparse Approximate Inverses (MSPAI) for Parallel Preconditioning. Doctoral Dissertation, Technische Universitat Munchen Zentrum Mathematik, Germany.
[20]
Tanaka, T. and Nodera, T. (2002) Effectiveness of Approximate Inverse Preconditioning by Using the MR Algorithm on an Origin 2400. In: Topping, B.H.V., Bittnar, Z., Topping, B.H.V. and Bittnar, Z., Eds., Proceedings of the 3rd International Conference on Engineering Computational Technology, Paper 44, 115-116.
http://dx.doi.org/10.4203/ccp.76.44
[21]
Lipitakis, E.A. (1983) A Normalized Sparse Linear Equations Solver. Journal of Computational and Applied Mathematics, 9, 287-298. http://dx.doi.org/10.1016/0377-0427(83)90021-3
[22]
Lipitakis, E.A. (1984) Generalized Extended to the Limit Sparse Factorization Techniques for Solving Unsymmetric Finite Element Systems. Computing, 32, 255-270. http://dx.doi.org/10.1007/BF02243576
[23]
Lipitakis, E.A. (1989) Numerical Solution of 3D Boundary Value Problems by Generalized Approximate Inverse Matrix Techniques. International Journal of Computer Mathematics, 31, 69-89.
http://dx.doi.org/10.1080/00207168908803789
[24]
Lipitakis, E.A. and Evans, D.J. (1979) Normalized Factorization Procedures for Solving Self-Adjoint Elliptic PDE’s in 3D Space Dimensions. Mathematics and Computers in Simulation, 21, 189-196.
http://dx.doi.org/10.1016/0378-4754(79)90133-2
[25]
Lipitakis, E.A. and Evans, D.J. (1980) Solving Non-Linear Elliptic Difference Equations by Extendable Sparse Factorization Procedures. Computing, 24, 325-339. http://dx.doi.org/10.1007/BF02237818
[26]
Lipitakis, E.A. and Evans, D.J. (1981) The Rate of Convergence of an Approximate Matrix Factorization Semi-Direct Method. Numerische Mathematik, 36, 237-251. http://dx.doi.org/10.1007/BF01396653
[27]
Lipitakis, E.A. and Evans, D.J. (1984) Solving Linear FE Systems by Normalized Approximate Matrix Factorization Semi-Direct Methods. Computer Methods in Applied Mechanics and Engineering, 43, 1-19.
http://dx.doi.org/10.1016/0045-7825(84)90091-4
[28]
Lipitakis, E.A. and Evans, D.J. (1987) Explicit Semi-Direct Methods Based on Approximate Inverse Matrix Techniques for Solving BV Problems on Parallel Processors. Mathematics and Computers in Simulation, 29, 1-17.
http://dx.doi.org/10.1016/0378-4754(87)90062-0
[29]
Gravvanis, G.A. (2000) Fast Explicit Approximate Inverses for Solving Linear and Non-Linear Finite Difference Equations. International Journal of Differential Equations and Applications, 1, 451-473.
[30]
Gravvanis, G.A. and Giannoutakis, K.M. (2005) Normalized Explicit Preconditioned Methods for Solving 3D Boundary Value Problems on Uniprocessor and Distributed Systems. International Journal for Numerical Methods in Engineering, 65, 84-110. http://dx.doi.org/10.1002/nme.1494
[31]
Gravvanis, G.A. and Gianoutakis, K.M. (2003) Normalized Explicit FE Approximate Inverses. International Journal of Differential Equations and Applications, 6, 253-267.
[32]
Pinter, G.F. and Gray, W.G. (1977) Finite Element Simulation in Surface Hydrology. Academic Press, New York.
[33]
Porsching, T.A. (1976) On the Origins and Numerical Solution of Some Sparse Non-Linear Systems. In: Bunch, J.R. and Rose, D.J., Eds., Sparse Matrix Computations, Academic Press, New York, 439.
[34]
Gravvanis, G.A. and Lipitakis, E.A. (1996) An Explicit Sparse Unsymmetric FE Solver. Communications in Numerical Methods in Engineering, 12, 21-29.
http://dx.doi.org/10.1002/(SICI)1099-0887(199601)12:1<21::AID-CNM948>3.0.CO;2-K
[35]
Gravvanis, G.A. (2000) Generalized Approximate Inverse Preconditioning for Solving Non-Linear Elliptic BV Problems. International Journal of Applied Mathematics, 2, 1363-1378.
[36]
Lipitakis, A.D. and Lipitakis, E.A.E.C. (2012) On the E-Valuation of Certain E-Business Strategies on Firm Performance by Adaptive Algorithmic Modelling: An Alternative Strategic Managerial Approach. Computer Technology and Application, 3, 38-46.
[37]
Bollhofer, M. (2003) A Robust and Efficient ILU that Incorporates the Growth of the Inverse Triangular Factors. SIAM Journal on Scientific Computing, 25, 86-103. http://dx.doi.org/10.1137/S1064827502403411
[38]
Cosgrove, J., Dias, J. and Griewank, A. (1992) Approximate Inverse Preconditioning for Sparse Linear Systems. International Journal of Computer Mathematics, 44, 91-110. http://dx.doi.org/10.1080/00207169208804097
[39]
Evans, D.J. (1967) The Use of Preconditioning in Iterative Methods for Solving Linear Equations with Symmetric Positive Definite Matrices. IMA Journal of Applied Mathematics, 4, 295-314.
Gravvanis, G.A. and Giannoutakis, K.M. (2003) Normalized FE Approximate Inverse Preconditioning for Solving Nonlinear BV Problems. In: Bathe, K.J., Ed., Computational Fluid and Solid Mechanics 2003, Proceedings of 2nd MIT Conference on Computational Fluid and Solid Mechanics, 2, 1958-1962.
[43]
Huckle, T. (1998) Efficient Computation of Sparse Approximate Inverses. Numerical Linear Algebra with Applications, 5, 57-71. http://dx.doi.org/10.1002/(SICI)1099-1506(199801/02)5:1<57::AID-NLA129>3.0.CO;2-C
[44]
Jia, Z. and Zhu, B. (2009) A Power Sparse Approximate Inverse Preconditioning Procedure for Large Sparse Linear Systems. Numerical Linear Algebra with Applications, 16, 259-299. http://dx.doi.org/10.1002/nla.614
[45]
Kolotilina, L.Y. and Yeremin, A.Y. (1993) Factorized Sparse Approximate Inverse Preconditioning. SIAM Journal on Matrix Analysis and Applications, 14, 45-58. http://dx.doi.org/10.1137/0614004
[46]
Tang, W.-P. and Wan, W.L. (2000) Sparse Approximate Inverse Smoother for Multigrid. SIAM Journal on Matrix Analysis and Applications, 21, 1236-1252. http://dx.doi.org/10.1137/S0895479899339342
[47]
Golub, G.H. and Van Loan, C. (1989) Matrix Computations. John Hopkins University Press, Baltimore.
[48]
Evans, D.J. and Lipitakis, E.A. (1980) A Normalized Implicit Conjugate Gradient Method for the Solution of Large Sparse Systems of Linear Equations. Computer Methods in Applied Mechanics and Engineering, 23, 1-19.
http://dx.doi.org/10.1016/0045-7825(80)90075-4
[49]
Giannoutakis, C.M. (2008) Study of Advanced Computational Methods of High Performance: Preconditioned Methods and Techniques of Matrix Inversion. Doctoral Thesis, Department of Electrical and Computer Engineering, Democritus University of Thrace, Hellas.
[50]
Tewarson, R.P. (1966) On the Product Form of Inverses of Sparse Matrices. SIAM Review, 8, 336-342.
http://dx.doi.org/10.1137/1008066
[51]
Lipitakis, A.D. (2016) A Generalized Exact Inverse Solver Based on Adaptive Algorithmic Methodologies for Solving Complex Computational Problems in Three Space Dimensions. HU-DP-TR15-2016, Technical Report.
[52]
Axelsson, O. (1985) A Survey of Preconditioned Iterative Methods of Linear Systems of Algebraic Equations. BIT Numerical Mathematics, 25, 166-187. http://dx.doi.org/10.1007/BF01934996
[53]
Saad, Y. and Van der Vorst, H.A. (2000) Iterative Solution of Linear Systems in the 20th Century. Journal of Computational and Applied Mathematics, 123, 1-33. http://dx.doi.org/10.1016/S0377-0427(00)00412-X
[54]
Chen, K. (2005) Matrix Preconditioning Techniques and Applications. Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, Cambridge. http://dx.doi.org/10.1017/CBO9780511543258
[55]
Axelsson, O., Carey, G. and Lindskog, G. (1985) On a Class of Preconditioned Iterative Methods for Parallel Computers. International Journal for Numerical Methods in Engineering, 27, 637-654.
http://dx.doi.org/10.1002/nme.1620270314
[56]
Benji, M. (2002) Preconditioning Techniques for Large Linear Systems: A Survey. Journal of Computational Physics, 182, 418-477. http://dx.doi.org/10.1006/jcph.2002.7176
[57]
Evans, D.J. (1972) The Analysis and Applications of Sparse Matrix Algorithms in FE Applications. In: Whiteman, J.R., Ed., Proceedings of Brunel University Conference, Academic Press, London and New York, 427-447.
[58]
Gravvanis, G.A. (2002) Explicit Approximate Inverse Preconditioning Techniques. Archives of Computational Methods in Engineering, 9, 371-402. http://dx.doi.org/10.1007/BF03041466
[59]
Thomas, L.H. (1949) Elliptic Problems in Linear Difference Equations over a Network. Watson Sc. Comp. Lab. Rep., Columbia University, New York.
