Solving large scale systems of linear equations with a stabilized Lanczos-type algorithms running on a cloud computing platform

Abstract

The Lanczos-type algorithms for Systems of Linear Equations (SLEs) are efficient but fragile. A number of ways to resolve this issue have been suggested. But, the problem is still not fully sorted, in our view. Here, we suggest a way that takes advantage of the sequence of approximate solutions that have been computed prior to breakdown by embedding interpolation/extrapolation to avoid it.  The approach, referred to as Embedded Interpolation-Extrapolation Model in Lanczos-type Algorithm (EIEMLA), generates new iterates which are at least as good as the best in the current sequence. This process is repeated after appending the new iterates to the sequence of approximate solutions until some convergence tolerance is achieved. To improve EIEMLA's convergence and stability, a restart version of REIEMLA is also considered. These algorithms are more robust than other Lanczos-type algorithms, including those with restarting and switching strategies. Both algorithms have been implemented to run in parallel on a Cloud computing platform. Our tests involve SLEs with up to $10^6$ variables and equations. The results show that breakdown is mitigated and efficiency gains can be achieved through parallelization.

Keywords

• Lanczos-type algorithm,breakdown,EIEMLA method,parallel processing,cloud computing

References

1. Ayachour, E., Avoiding Look-Ahead in Lanczos Method and Pade Approximation, Applicationes Mathematica, 1999.
2. Baheux, C. New implementations of Lanczos method, Journal of Computational and Applied Mathematics 57 (1-2), 3-15, 1995.
3. Brezinski, C., Sadok, H., Lanczos-type algorithms for solving systems of linear equations, Applied Numerical Mathematics 11 (6), 443-473, 1993.
4. Brezinski, C. and Zaglia, R. A New Presentation of Orthogonal Polynomials with Applications to Their Computation, Numerical Algorithms 1 (2), 207-221, 1991.
5. Brezinski, C. and Zaglia, R. Breakdowns in the Computation of Orthogonal Polynomials, Springer, Dordrech 296, 49-59, 1994.
6. Brezinski, C. and Zaglia, R. and Sadok, H., Avoiding Breakdown and Near-Breakdown in Lanczos-type Algorithms, Numerical Algorithms 1 (2), 261-284, 1991.
7. Brezinski, C. and Zaglia, R. and Sadok, H., A Breakdown-Free Lanczos-type Algorithm for Solving Linear Systems, Numerical Mathematics 63 (1), 29-38, 1992.
8. Brezinski, C. and Zaglia, R. and Sadok, H., New Look - Ahead Lanczos - type Algorithms for Linear Systems, Numerical Mathematics 83, 53-85, 2000.

9. Brezinski, C. and Zaglia, R. and Sadok, H., The Matrix and Polynomial Approaches to Lanczos-type Algorithms, Journal Of Computational and Applied Mathematics 123 (1-2), 241-260, 2000.
10. Buyya, R., Broberg, J., Goscinski, A., Cloud Computing Principles and Paradigms, John Wiley and Sons, (1-2), 241-260, 2011.
11. Duff, L.S., Van der Vorst, H. A., Developments and Trends in the Parallel Solution of Linear Systems, Parallel Computing 25, 1931-1970, 1999.
12. Elprin, Nick Private Discussion, 11 August 2014.
13. Elprin, Nick Domino: A Platform-as-a-Service for Industrialized Data Analysi, http:/www.help.dominodatalab.com/keyConcepts, 2014.
14. Farooq, M., Salhi, A., TNew Recurrence Relationships between Orthogonal Polynomials which Lead to New Lanczos-type Algorithms, Journal of Prime Research in Mathematics 8, 61-75, 20012.
15. Farooq, M., Salhi, A., A Preemptive Restarting Approach to Beating Inherent Instability, Iranian Journal of Science and Technology Transaction a Science 37, (Special Issue) 349-358, 2013.
16. Farooq, M., Salhi, A., A Switching Approach to Avoid Breakdown in Lanczos-type Algorithms, Applied Mathematics and Information Sciences 8, (5) 2161-2169, 2014.
17. Fritsch, F. N., Butland, J., A Method for Constructing Local Monotone Piecewise Cubic Interpolants, SIAM J. Sci. Stat. Comput. 5, (2) 300-304, 1984.
18. Fritsch, F. N., Carlson, R.E., Monotone Piecewise Cubic Interpolation, SIAM Journal Numerical Analysis 17, (2) 239-248, 1980.
19. Grave-Morris, P., A Look-Around Lanczos Algorithm for Solving a System of Linear Equations, Numerical Algorithm 15, 247-274, 1997.
20. Heller, D., A Survey of Parallel Algorithms in Numerical Linear Algebra, Technical report, Department of Computer Science, Carnegie Mellon University 1-1-1976, http://repository.cmu.edu/compsci, 1976.
21. Huth, A., Cebula The Basics of Cloud Computing, Technical report, Produced for US-CERT, Carnegie Mellon University, www.us-cert.gov/sites/default/files/.../CloudComputingHuthCebula.pdf, 2011.
22. Lanczos, C., An Iteration Method for The Solution of the Eigenvalue Problem of Linear Differential and Integral Operator, J.Res.Natl.Bur.Stand 45, (4), 255-282, 1958.
23. Lanczos, C., Solution of Systems of Linear Equations by Minimized Iterations, J. Res. Natl .Bur. Stand 49, (1), 33-53, 1952.
24. Landis, C., Blacharski, D., Cloud Computing Made Easy, Virtual Global Inc., 2013.
25. Maharani, M., Salhi, A., Restarting from Specific Points to Cure Breakdown in Lanczos-type Algorithms, Journal of Mathematical and Fundamental Sciences 2, (47), 167-184, 2015.
26. Maharani, M., Salhi, A., Khan, W., Enhanced the Stability of Lanczos-type Algorithms by Restarting The Point Generated by EIEMLA for the Solution of Systems of Linear Equations, Sci.Int.(Lahore) 28, (4), 3325-3335, 2016.
27. Rajalakshami, K., Parallel Algorithm for Solving Large Systems of Simultaneous Linear Equations, IJCSNS 9, (7), 276-279, 2009.
28. Rashid, M., Crowcroft, J., Parallel Iterative Solution Method for Large Sparse Linear Equation Systemss, Tech. Rep. 650, Technical report, University of Cambridge, Computer Laboratory, October 2005.
29. Saad, Y., Iterative Methods for Sparse Linear Systems, Philadelphia: Society for Industrial and Applied Mathematics, 2003.
30. Salhi, A., Proll, L. G., Rios Insua, D., Parallelising an Optimisation-based Framework for Sensitivity Analysis in MultiCriteria Decision Making, Tech. Rep. 98-15, Mathematics Department, University of Essex, UK, 1998.
31. Sidi, A., William Ford, F., David Smith, A., Acceleration of Convergence of Vector Sequences, SIAM Journal on Numerical Analysis 23, (1), 178–196, 1986.
32. Torp, A., Sparse Linear Algebra on a GPU with Applications to Flow in Porous Media, Ph.D. thesis, Department of Physics and Mathematics, Norwegian University of Science and Technology, 2009.