Explicit Iterative Methods of Second Order and Approximate Inverse Preconditioners for Solving Complex Computational Problems
Abstract: 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.
Cite this paper: Lipitakis, A. (2020) Explicit Iterative Methods of Second Order and Approximate Inverse Preconditioners for Solving Complex Computational Problems. Applied Mathematics, 11, 307-327. doi: 10.4236/am.2020.114023.
References

[1]   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

[2]   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

[3]   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

[4]   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

[5]   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.

[6]   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

[7]   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

[8]   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

[9]   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

[10]   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

[11]   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

[12]   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

[13]   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

[14]   Saad, Y. (2004) Iterative Methods for Sparse Linear Systems. SIAM, Philadelphia.
https://doi.org/10.1137/1.9780898718003

[15]   Varga, R.S. (1962) Matrix Iterative Analysis. Prentice-Hall, Upper Saddle River.

[16]   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

[17]   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

[18]   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

[19]   Young, D.M. (1971) Iterative Solution of Large Linear Systems. Academic Press, New York.

[20]   Fadeev, D.K. and Fadeeva, V.N. (1963) Computational Methods in Linear Algebra. W.H. Freeman and Company, San Francisco.

[21]   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

[22]   Kincaid, D.R. (1972) On Complex Second-Degree Iterative Methods. SIAM Journal on Numerical Analysis, 11, 211-218.
https://doi.org/10.1137/0711020

[23]   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

[24]   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

[25]   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.

[26]   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.

[27]   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

[28]   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

[29]   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

[30]   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.

[32]   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

[33]   Goldreich, O. (2008) Computational Complexity: A Conceptual Perspective. Cambridge University Press, Cambridge.
https://doi.org/10.1017/CBO9780511804106

[34]   Arora, S. and Barak, B. (2009) Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge.
https://doi.org/10.1017/CBO9780511804090

[35]   Nocedal, J. and Wright, S. (2006) Numerical Optimization. 2nd Edition, Springer, New York.

[36]   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

[37]   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.

[38]   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

[39]   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

[40]   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

[41]   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

[42]   Axelsson, O. (1994) Iterative Solution Methods. Cambridge University Press, Cambridge.
https://doi.org/10.1017/CBO9780511624100

[43]   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

[44]   Marchuk, G.I. (1975) Methods of Numerical Mathematics. Springer-Verlag, Berlin.
https://doi.org/10.1007/978-1-4615-9988-3

[45]   Yanenko, N.N. (1971) The Method of Fractional Steps. Springer-Verlag, Berlin.
https://doi.org/10.1007/978-3-642-65108-3

[46]   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

[47]   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.

[48]   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.

Top