Explicit Iterative Methods of Second Order and Approximate Inverse Preconditioners for Solving Complex Computational Problems — Oak Academic Publishing
Research ArticleOpen AccessGoogle Scholar indexed
Explicit Iterative Methods of Second Order and Approximate Inverse Preconditioners for Solving Complex Computational Problems
Department of Informatics and Telematics, Harokopio University, Athens, Greece
1 Department of Informatics and Telematics, Harokopio University, Athens, Greece
Explicit Exact and Approximate Inverse Preconditioners for solving complex linear systems are introduced. A class of general iterative methods of second order is presented and the selection of iterative parameters is discussed. The second order iterative methods behave quite similar to first order methods and the development of efficient preconditioners for solving the original linear system is a decisive factor for making the second order iterative methods superior to the first order iterative methods. Adaptive preconditioned Conjugate Gradient methods using explicit approximate preconditioners for solving efficiently large sparse systems of algebraic equations are also presented. The generalized Approximate Inverse Matrix techniques can be efficiently used in conjunction with explicit iterative schemes leading to effective composite semi-direct solution methods for solving large linear systems of algebraic equations.
Hestenes, M.R. and Stiefel, E. (1952) Methods of Conjugate Gradients for Solving Linear Systems. Journal of Research National Bureau Standards, 49, 409-436. https://doi.org/10.6028/jres.049.044
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. https://doi.org/10.1016/0045-7825(80)90075-4
Saad, Y. and Schultz, M.H. (1985) Conjugate Gradient-Like Algorithms for Solving Nonsymmetric Linear Systems. Mathematics of Computation, 44, 417-424. https://doi.org/10.1090/S0025-5718-1985-0777273-9
Lipitakis, E.A. and Gravvanis, G.A. (1992) A Class of Explicit Preconditioned Conjugate Gradient Methods for Solving Large Finite Element Systems. International Journal of Computer Mathematics, 44, 189-206. https://doi.org/10.1080/00207169208804104
Gustafsson, I. (1983) Modified Incomplete Cholesky (MIC) Methods. In: Evans, D.J., Ed., Preconditioning Methods, Theory and Applications, Gordon and Breach Science Publishers, New York, 265-293.
van Leeuwen, J. (1990) Handbook of Theoretical Computer Science (Vol. A) Algorithms and Complexity. MIT Press, Cambridge. https://doi.org/10.1016/B978-0-444-88071-0.50015-1
Yeremin, A.Y., Kolotilina, L.Y. and Nikishin, A.A. (2000) Factorized Sparse Approximate Inverse Preconditionings III. Iterative Construction of Preconditioners. Computational Methods and Algorithms. Part XIII, Zap. Nauchn. Sem. POMI 248, POMI, St. Petersburg, 1998, 17-48. Journal of Mathematical Sciences (New York), 101, 3237-3254. https://doi.org/10.1007/BF02672769
Benzi, M. (2002) Preconditioning Techniques for Large Linear Systems: A Survey. Journal of Computational Physics, 182, 418-477. https://doi.org/10.1006/jcph.2002.7176
Benzi, M., Meyer, C.D. and Tůma, M. (1996) A Sparse Approximate Inverse Preconditioner for the Conjugate Gradient Method. SIAM Journal on Scientific Computing, 17, 1135-1149. https://doi.org/10.1137/S1064827594271421
Meijerink, J. and van der Vorst, H.A. (1981) Guidelines for the Usage of Incomplete Decompositions in Solving Sets of Linear Equations as They Occur in Practical Problems. Journal of Computational Physics, 44, 134-155. https://doi.org/10.1016/0021-9991(81)90041-3
Evans, D.J. and Forrington, C.V.D. (1963) An Iterative Process for Optimizing Symmetric Successive Over-Relaxation. The Computer Journal, 6, 271-273. https://doi.org/10.1093/comjnl/6.3.271
Manteuffel, T.A. (1980) An Incomplete Factorization Technique for Positive Definite Linear Systems. Mathematics of Computation, 34, 473-497. https://doi.org/10.1090/S0025-5718-1980-0559197-0
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. https://doi.org/10.1016/0378-4754(87)90062-0
Saad, Y. (2004) Iterative Methods for Sparse Linear Systems. SIAM, Philadelphia. https://doi.org/10.1137/1.9780898718003
Golub, G.H. (1961) Semi-Iterative Methods, Successive Over-Relaxation Iterative Methods, and Second-Order Richardson Iterative Methods. I, II. Numerische Mathematik, 3, 147-168. https://doi.org/10.1007/BF01386014
Peaceman, D.W. and Rachford, H.H. (1955) The Numerical Solution of Parabolic and Elliptic Differential Equations. Journal of the Society for Industrial and Applied Mathematics, 3, 28-41. https://doi.org/10.1137/0103003
Young, D. (1972) Second-Degree Iterative Methods for the Solution of Large Linear Systems. Journal of Approximation Theory, 5, 137-148. https://doi.org/10.1016/0021-9045(72)90036-6
Young, D.M. (1971) Iterative Solution of Large Linear Systems. Academic Press, New York.
Fadeev, D.K. and Fadeeva, V.N. (1963) Computational Methods in Linear Algebra. W.H. Freeman and Company, San Francisco.
Niethammer, W., de Pillis, J. and Varga, R.S. (1984) Block Iterative Methods Applied to Sparse Least-Squares Problems. Linear Algebra and Its Applications, 58, 327-341. https://doi.org/10.1016/0024-3795(84)90218-0
Kincaid, D.R. (1972) On Complex Second-Degree Iterative Methods. SIAM Journal on Numerical Analysis, 11, 211-218. https://doi.org/10.1137/0711020
Kang, S.M., Rafiq, A. and Kwun, Y.C. (2013) A New Second-Order Iteration Method for Solving Nonlinear Equations. Abstract and Applied Analysis, 2013, Article ID: 487062. https://doi.org/10.1155/2013/487062
Kogan, T., Sapir, L. and Sapir, A. (2007) A Nonstationary Iterative Second-Order Method for Solving Nonlinear Equations. Applied Mathematics and Computation, 188, 75-82. https://doi.org/10.1016/j.amc.2006.09.092
Newton, I. (1711) A Treatise of Algebra Both Historical and Practical, Published by John Wallis; De analysi per aequationes numero terminorum infinitas (Written in 1669, Published in 1711 by William Jones) and in De metodisfluxionum et serieruminfinitarum (Written in 1671, Translated and Published as Method of Fluxions in 1736 by John Colson), 1685.
Khan, W.A., Noor, M.A. and Rauf, A. (2015) Second Derivatives Free Fourth-Order Iterative Method Solving for Nonlinear Equation. Applied Mathematics, 5, 15-20.
Antipin, A.S., Mijailovic, N. and Jacimovic, M. (2013) A Second-Order Iterative Method for Solving Quasi-Variational Inequalities. Computational Mathematics and Mathematical Physics, 53, 258-264. https://doi.org/10.1134/S0965542513030032
Saqib, M., Igbal, M., Ahmed, S., Ali, S. and Ismael, T. (2015) New Modification of Fixed Point Iterative Method for Solving Nonlinear Equations. Applied Mathematics, 6, 1857-1863. https://doi.org/10.4236/am.2015.611163
Zhong, Y. and Wong, M.D.F. (2007) Efficient Second-Order Iterative Methods for IR Drop Analysis in Power Grid. Department of Electrical and Computer Engineering University of Illinois at Urbana-Champaign, Champaign. https://doi.org/10.1109/ASPDAC.2007.358082
Lipitakis, A. and Lipitakis, E.A.E.C. (2014) E-Business Performance and Strategy Planning E-Valuation Based on Adaptive Algorithmic Modelling Methods: Critical Factors Affecting E-Valuation and Strategic Management Methodologies. Universal Journal of Management, 2, 81-91.
Papadimitriou, C. (1994) Computational Complexity. Addison Wesley, Boston.
Blondel, V.D. and Tsitsiklis, J.N. (2000) A Survey of Computational Complexity Results in Systems and Control. Automatica, 36, 1249-1274. https://doi.org/10.1016/S0005-1098(00)00050-9
Goldreich, O. (2008) Computational Complexity: A Conceptual Perspective. Cambridge University Press, Cambridge. https://doi.org/10.1017/CBO9780511804106
Arora, S. and Barak, B. (2009) Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge. https://doi.org/10.1017/CBO9780511804090
Nocedal, J. and Wright, S. (2006) Numerical Optimization. 2nd Edition, Springer, New York.
Sastry, S.P., Shontz, S.M. and Vavasis, S.A. (2014) A Log-Barrier Method for Mesh Quality Improvement and Untangling. Engineering with Computers, 30, 315-329. https://doi.org/10.1007/s00366-012-0294-6
Lipitakis, E.A. (1990) Euclid’s Algorithm and Accelerated Iterative Methods. Special Issue on Computer Mathematics, Bulletin of the Greek Mathematical Society, 31, 51-76.
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. https://doi.org/10.1007/BF01396653
Lipitakis, E.A. (1984) Generalized Extended to the Limit Sparse Factorization Techniques for Solving Large Unsymmetric Finite Element Systems. Computing, 32, 255-270. https://doi.org/10.1007/BF02243576
Lipitakis, E.A. (1984) The Use of Second Degree Normalized Implicit CG Methods for Solving Large Sparse Systems of Linear Equations. Journal of Computational and Applied Mathematics, 11, 39-47. https://doi.org/10.1016/0377-0427(84)90030-X
Douglas, J. and Rachford, H.H. (1956) On the Numerical Solution of Heat Conduction Problems in Two or Three Space Variables. Transactions of the American Mathematical Society, 82, 421-439. https://doi.org/10.1090/S0002-9947-1956-0084194-4
Axelsson, O. (1994) Iterative Solution Methods. Cambridge University Press, Cambridge. https://doi.org/10.1017/CBO9780511624100
Evans, D.J. (1985) Group Explicit Iterative Methods for Solving Large Linear Systems. International Journal of Computer Mathematics, 17, 81-108. https://doi.org/10.1080/00207168508803452
Marchuk, G.I. (1975) Methods of Numerical Mathematics. Springer-Verlag, Berlin. https://doi.org/10.1007/978-1-4615-9988-3
Yanenko, N.N. (1971) The Method of Fractional Steps. Springer-Verlag, Berlin. https://doi.org/10.1007/978-3-642-65108-3
Howes, F.A. (1986) Multidimensional Initial Boundary Value Problems with Strong Nonlinearities. Archive for Rational Mechanics and Analysis, 91, 153-168. https://doi.org/10.1007/BF00276861
Papadopoulos, A.T., Duff, I.S. and Wathen, A.J. (2002) Incomplete Orthogonal Factorization Methods Using Givens Rotations II: Implementation and Results. Tech. Report 02/07, Oxford University Computing Laboratory, Oxford.
Lipitakis, A.-D. (2020) Stability and Correctness of Incomplete Factorization Methods. ADL-HU-DP-TR47, Depart. of Informatics and Telematics, Harokopio University of Athens, Athens.