The effect of graph partitioning techniques on parallel Block FSAI preconditioning: a computational study

详细信息    查看全文

• 作者：Carlo Janna (1)
  Nicola Castelletto (2)
  Massimiliano Ferronato (1)
  
  1. Department ICEA ; University of Padova ; via Trieste 63 ; 35121 ; Padova ; Italy
  2. Department Energy Resources Engineering ; Stanford University ; 367 Panama St. ; Stanford ; CA ; 94305-2220 ; USA
  
• 关键词：Linear systems ; Iterative methods ; Preconditioning ; Parallel computing ; 65F08 ; 65F10 ; 65Y05 ; 68W10
• 刊名：Numerical Algorithms
• 出版年：2015
• 出版时间：April 2015
• 年：2015
• 卷：68
• 期：4
• 页码：813-836
• 全文大小：2,274 KB
• 参考文献：1. Cerd脿n, J, Faraj, T, Malla, N, Marin, J, Mas, J (2010) Block approximate inverse preconditioners for sparse nonsymmetric linear systems. Electron. Trans. Numer. Anal. 37: pp. 23-40
  2. Bergamaschi, L, Martinez, A (2011) FSAI-based parallel Mixed Constraint Preconditioners for saddle point problems arising in geomechanics. J. Comput. Appl. Math. 236: pp. 308-318 CrossRef
  3. Lazarov, BS, Sigmund, O (2011) Factored parallel preconditioner for the saddle point problem. Int. J. Numer. Methods Biomed. Eng. 27: pp. 1398-1410
  4. Ferronato, M, Janna, C, Pini, G (2012) Parallel solution to ill-conditioned FE geomechanical problems. Int. J. Numer. Anal. Methods Geomech. 36: pp. 422-437 CrossRef
  5. Ferronato, M, Janna, C, Pini, G (2012) Shifted FSAI preconditioners for the efficient parallel solution of non-linear groundwater flow models. Int. J. Numer. Methods Eng. 89: pp. 1707-1719 CrossRef
  6. Janna, C, Ferronato, M, Gambolati, G (2012) Parallel inexact constraint preconditioning for ill-conditioned consolidation problems. Comput. Geosci. 16: pp. 661-675 CrossRef
  7. Ferronato, M.: Preconditioning for sparse linear systems at the dawn of the 21st century: history, current developments, and future perspectives. ISRN Appl. Math. (2012). doi:10.5402/2012/127647
  8. Janna, C, Ferronato, M, Gambolati, G (2010) A Block FSAI-ILU parallel preconditioner for symmetric positive definite linear systems. SIAM J. Sci. Comput. 32: pp. 2468-2484 CrossRef
  9. Janna, C, Ferronato, M (2011) Adaptive pattern research for Block FSAI preconditioning. SIAM J. Sci. Comput. 33: pp. 3357-3380 CrossRef
  10. Ferronato, M, Janna, C, Pini, G (2012) Efficient parallel solution to large size sparse eigenproblems with Block FSAI preconditioning. Numer. Linear Algebra Appl. 19: pp. 797-815 CrossRef
  11. Janna, C, Ferronato, M, Gambolati, G (2013) Enhanced Block FSAI preconditioning using domain decomposition. SIAM J. Sci. Comput. 35: pp. S229-S249 CrossRef
  12. Ferronato, M, Janna, C, Pini, G (2014) A generalized Block FSAI preconditioner for nonsymmetric linear systems. J. Comput. Appl. Math. 256: pp. 230-241 CrossRef
  13. Kolotilina, LY, Yeremin, AY (1993) Factorized sparse approximate inverse preconditioning. I. Theory. SIAM J. Matrix Anal. Appl. 14: pp. 45-58 CrossRef
  14. Benzi, M, Szyld, DB, Duin, A (1999) Orderings for incomplete factorization preconditioning of nonsymmetric problems. SIAM J. Sci. Comput. 20: pp. 1652-1670 CrossRef
  15. Benzi, M, T暖ma, M (2000) Orderings for factorized sparse approximate inverse preconditioners. SIAM J. Sci. Comput. 21: pp. 1851-1868 CrossRef
  16. Cullum, JK, Johnson, K, T暖ma, M (2003) Effects of problem decomposition (partitioning) on the rate of convergence of parallel numerical algorithms. Numer. Linear Algebra Appl. 10: pp. 445-465 CrossRef
  17. Cuthill, E., McKee, J.: Reducing the bandwidth of sparse symmetric matrices. In: Proceedings of the 1969 24th National Conference, pp. 157鈥?72 (1969)
  18. George, A (1971) Computer Implementation of the Finite Element Method. Tech. Rep. STAN-CS-208. Department of Computer Science, Stanford University, Stanford
  19. Georges, JA, Liu, JW (1981) Computer Solution of Large Sparse Positive Definite Systems. Prentice-Hall, Englewood Cliffs
  20. Tinney, WF, Walker, JW (1967) Direct solutions of sparse network equations by optimally ordered triangular factorization. Proc. IEEE 55: pp. 1801-1809 CrossRef
  21. George, A, Liu, JW (1989) The evolution of the minimum degree ordering algorithm. SIAM Rev. 31: pp. 1-19 CrossRef
  22. Amestoy, P, Davis, T, Duff, I (1996) An approximate minimum degree ordering algorithm. SIAM J. Matrix Anal. Appl. 17: pp. 886-905 CrossRef
  23. Barnard, S, Simon, HD (1994) A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems. Concurr Pract Experience 6: pp. 101-117 CrossRef
  24. Hendrickson, B., Leland, R.: A multilevel algorithm for partitioning graphs. In: Proceedings of the ACM/IEEE Conference on Supercomputing (1995)
  25. Karypis, G, Kumar, V (1998) Multilevel k-way partitioning scheme for irregular graphs. J. Parallel Distrib. Comput. 48: pp. 96-129 CrossRef
  26. Karypis, G, Kumar, V (1999) A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20: pp. 359-392 CrossRef
  27. Chevalier, C., Pellegrini, F.: Improvement of the efficiency of genetic algorithms for scalable parallel graph partitioning in a multi-level framework. In: Proceedings of EuroPar 2006. Lecture Notes on Computer Science, no. 4128, pp. 243鈥?52 (2006)
  28. Pellegrini, F.: A parallelisable multi-level banded diffusion scheme for computing balanced partitions with smooth boundaries. In: Proceedings of EuroPar 2007. Lecture Notes on Computer Science, no. 4641, pp. 191鈥?00 (2007)
  29. Pellegrini, F.: SCOTCH, software package and libraries for sequential and parallel graph partitioning, static mapping, and sparse matrix block ordering, and sequential mesh and hypergraph partitioning (version 5.1.10). Electronic document available at http://www.labri.fr/perso/pelegrin/scotch (2010)
  30. Karypis, G., Kumar, V.: METIS - A software package for partitioning unstructured graphs, partitioning meshes and computing fill-reducing orderings of sparse matrices - Version 5.0. Electronic document available at http://glaros.dtc.umn.edu/gkhome/metis/metis/overview (2011)
  31. Holland, RM, Wathen, AJ, Shaw, GJ (2005) Sparse approximate inverses and target matrices. SIAM J. Sci. Comput. 26: pp. 1000-1011 CrossRef
  32. Saad, Y (1994) ILUT: a dual threshold incomplete ILU factorization. Numer. Linear Algebra Appl. 1: pp. 387-402 CrossRef
  33. Li, N, Saad, Y, Chow, E (2003) Crout version of ILU for general sparse matrices. SIAM J. Sci. Comput. 25: pp. 716-728 CrossRef
  34. Janna, C, Comerlati, A, Gambolati, G (2009) A comparison of projective and direct solvers for finite elements in elastostatics. Adv. Eng. Softw. 40: pp. 675-685 CrossRef
  35. Chow, E (2000) A priori sparsity patterns for parallel sparse approximate inverse preconditioners. SIAM J. Sci. Comput. 21: pp. 1804-1822 CrossRef
  36. Grote, M, Huckle, T (1997) Parallel preconditioning with sparse approximate inverses. SIAM J. Sci. Comput. 18: pp. 838-853 CrossRef
  37. Huckle, T (1999) Approximate sparsity patterns for the inverse of a matrix and preconditioning. Appl. Numer. Math. 30: pp. 291-303 CrossRef
  38. Huckle, T (2003) Factorized sparse approximate inverses for preconditioning. J. Supercomput. 25: pp. 109-117 CrossRef
  39. Kaporin, IE (1994) New convergence results and preconditioning strategies for the conjugate gradient method. Numer. Linear Algebra Appl. 1: pp. 179-210 CrossRef
  40. Anderson, G, Bai, Z, Bischof, C, Demmel, J, Dongarra, J, Du Croz, J, Greenbaum, A, Kenney, AM, Ostrouchov, S, Sorensen, D (1992) LAPACK User鈥檚 Guide. SIAM, Philadelphia
  41. Bridson, R, Tang, WP (1999) Ordering, anisotropy and factored sparse approximate inverses. SIAM J. Sci. Comput. 21: pp. 867-882 CrossRef
  42. Saad, Y (2003) Iterative Methods for Sparse Linear Systems. SIAM, Philadelphia CrossRef
  43. Saad, Y.: SPARSKIT, a basic tool-kit for sparse matrix computations (Version 2). Electronic document available at http://www-users.cs.umn.edu/~saad/software/SPARSKIT (1988)
  44. Kernighan, BW, Lin, S (1970) An efficient heuristic procedure for partitioning graphs. Bell Syst. Technol. J. 49: pp. 291-307 CrossRef
  45. Duff, IS, Kaya, K (2013) Preconditioners based on strong subgraphs. Electron. Trans. Numer. Anal. 40: pp. 225-249
  46. Vecharinsky, E, Saad, Y, Sosonika, M (2014) Graph partitioning using matrix values for preconditioning symmetric positive definite systems. SIAM J. Sci. Comput. 36: pp. A63-A87 CrossRef
  47. Teatini, P, Ferronato, M, Gambolati, G, Ba霉, D, Putti, M (2010) Anthropogenic Venice uplift by seawater pumping into a heterogeneous aquifer system. Water Resour. Res. 46: pp. W11547
  48. Ferronato, M, Gambolati, G, Janna, C, Teatini, P (2010) Geomechanical issues of anthropogenic CO2 sequestration in exploited gas fields. Energy Convers. Manag. 51: pp. 1918-1928 CrossRef
  49. Davis, TA, Hu, Y (2011) The University of Florida Sparse Matrix Collection. ACM Trans. Math. Softw. 38: pp. 1-25
  
• 刊物类别：Computer Science
• 刊物主题：Numeric Computing
  Algorithms
  Mathematics
  Algebra
  Theory of Computation
  
• 出版者：Springer U.S.
• ISSN：1572-9265

文摘

Adaptive Block FSAI (ABF) is a novel preconditioner which has proved efficient for the parallel solution of symmetric positive definite (SPD) linear systems and eigenproblems. A possible drawback stems from its reduced strong scalability, as the iteration count to converge for a given problem tends to grow with the number of processors used. The preliminary use of graph partitioning techniques can help improve the preconditioner quality and scalability. According to the specific theoretical properties of Block FSAI, different partitionings are selected and tested in a set of matrices arising from SPD engineering applications. The results show that using an appropriate graph partitioning technique with ABF may play an important role to increase the preconditioner efficiency and robustness, allowing for its effective use also in massively parallel simulations.