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 — Oak Academic Publishing
Research ArticleOpen AccessGoogle Scholar indexed
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
Department of Informatics and Telematics, Harokopio University, Athens, Greece
1 Department of Informatics and Telematics, Harokopio University, Athens, Greece
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.
KeywordsAdaptive AlgorithmsAlgorithmic ModellingApproximate InverseIncomplete LU FactorizationApproximate DecompositionUnsymmetric Linear SystemsPreconditioned Iterative MethodsSystems of Irregular Structure
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
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
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
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.
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
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
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
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
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
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
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
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
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
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
Van der Vorst, H.A. (1989) High Performance Preconditioning. SIAM Journal on Scientific Computing, 10, 1174-1185. http://dx.doi.org/10.1137/0910071
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
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
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
Kallischko, A. (2008) Modified Sparse Approximate Inverses (MSPAI) for Parallel Preconditioning. Doctoral Dissertation, Technische Universitat Munchen Zentrum Mathematik, Germany.
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
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
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
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
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
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
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
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
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
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.
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
Gravvanis, G.A. and Gianoutakis, K.M. (2003) Normalized Explicit FE Approximate Inverses. International Journal of Differential Equations and Applications, 6, 253-267.
Pinter, G.F. and Gray, W.G. (1977) Finite Element Simulation in Surface Hydrology. Academic Press, New York.
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.
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 3.0.CO;2-K
Gravvanis, G.A. (2000) Generalized Approximate Inverse Preconditioning for Solving Non-Linear Elliptic BV Problems. International Journal of Applied Mathematics, 2, 1363-1378.
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.
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
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
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.
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 3.0.CO;2-C
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
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
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
Golub, G.H. and Van Loan, C. (1989) Matrix Computations. John Hopkins University Press, Baltimore.
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
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.
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
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.
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
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
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
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
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
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.
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
Thomas, L.H. (1949) Elliptic Problems in Linear Difference Equations over a Network. Watson Sc. Comp. Lab. Rep., Columbia University, New York.