More Web Proxy on the site http://driver.im/

research-article

Parallel design and performance of nested filtering factorization preconditioner

Authors:

Frédéric NatafAuthors Info & Claims

SC '13: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis

Article No.: 81, Pages 1 - 12

https://doi.org/10.1145/2503210.2503287

Published: 17 November 2013 Publication History

Abstract

We present the parallel design and performance of the nested filtering factorization preconditioner (NFF), which can be used for solving linear systems arising from the discretization of a system of PDEs on unstructured grids. NFF has limited memory requirements, and it is based on a two level recursive decomposition that exploits a nested block arrow structure of the input matrix, obtained priorly by using graph partitioning techniques. It also allows to preserve several directions of interest of the input matrix to alleviate the effect of low frequency modes on the convergence of iterative methods. For a boundary value problem with highly heterogeneous coefficients, discretized on three-dimensional grids with 64 millions unknowns and 447 millions nonzero entries, we show experimentally that NFF scales up to 2048 cores of Genci's Bull system (Curie), and it is up to 2.6 times faster than the domain decomposition preconditioner Restricted Additive Schwarz implemented in PETSc.

References

[1]

Y. Achdou and F. Nataf. An iterated tangential filtering decomposition. Numer. Linear Algebra Appl., 10(5-6):511--539, 2003. Preconditioning, 2001 (Tahoe City, CA).

[2]

Y. Achdou and F. Nataf. Low frequency tangential filtering decomposition. Numer. Linear Algebra Appl., 14(2):129--147, 2007.

[3]

P. R. Amestoy, I. S. Duff, J. Koster, and J.-Y. L'Excellent. A fully asynchronous multifrontal solver using distributed dynamic scheduling. SIAM Journal on Matrix Analysis and Applications, 23(1):15--41, 2001.

Digital Library

[4]

J. Appleyard and I. Cheshire. Nested factorization. In Seventh SPE Symposium on Reservoir Simulation, pages 315--324, 1983. paper number 12264.

[5]

S. Balay, J. Brown, K. Buschelman, W. D. Gropp, D. Kaushik, M. G. Knepley, L. C. McInnes, B. F. Smith, and H. Zhang. PETSc Web page, 2012. http://www.mcs.anl.gov/petsc.

[6]

A. Brandt, J. Brannick, K. Kahl, and I. Livshits. Bootstrap AMG. SIAM J. Sci. Comput., 33(2):612--632, 2011.

Digital Library

[7]

I. S. Duff, M. A. Heroux, and R. Pozo. An overview of the sparse basic linear algebra subprograms: The new standard from the blas technical forum. ACM Trans. Math. Softw., 28(2):239--267, June 2002.

Digital Library

[8]

R. Fezzani, L. Grigori, F. Nataf, and K. Wang. Block Filtering Decomposition. In Numerical Linear Algebra with Applications (NLAA), submitted 2012.

[9]

J. A. George, J. W. H. Liu, and E. G. Ng. Communication results for parallel sparse Cholesky factorization on a hypercube. Parallel Computing, 10:287--298, 1989.

[10]

L. Grigori, P. Kumar, F. Nataf, and K. Wang. A class of multilevel parallel preconditioning strategies. Research Report RR-7410, INRIA, Oct. 2010.

[11]

L. Grigori and F. Nataf. Generalized Filtering Decomposition. Research Report RR-7569, INRIA, Mar. 2011.

[12]

L. Grigori, F. Nataf, and P. Kumar. Multipurpose Calculation Computing Device, 2010. FR Patent WO/2012/035272 filed September 17, 2010, International Application No. PCT/FR2011/052128.

[13]

L. Grigori, F. Nataf, and L. Qu. Overlapping for preconditioners based on incomplete factorizations and nested dissection. In Numer. Linear Algebra Appl., submitted 2012.

[14]

M. Gu, X. S. Li, and P. S. Vassilevski. Direction-preserving and Schur-monotonic semiseparable approximations of symmetric positive definite matrices. SIAM J. Matrix Anal. Appl., 31(5):2650--2664, 2010.

Digital Library

[15]

G. Karypis and V. Kumar. A software package for partitioning unstructured graphs, partitioning meshes and computing fill-reducing orderings of sparse matrices - verstion 4.0, 1998. See http://www-users.cs.umn.edu/karypis/metis.

[16]

P. Kumar. A class of preconditioning techniques suitable for partial differential equations on structured and unstructured mesh. PhD thesis, University Paris-Sud XI, 2010. Inria Saclay - Ile de France.

[17]

P. Kumar, K. Meerbergen, and D. Roose. Multi-threaded nested filtering factorization preconditioner. In P. Manninen and P. Oster, editors, Applied Parallel and Scientific Computing, volume 7782 of Lecture Notes in Computer Science, pages 220--234. Springer Berlin Heidelberg, 2013.

Digital Library

[18]

Q. Niu, L. Grigori, P. Kumar, and F. Nataf. Modified tangential frequency filtering decomposition and its fourier analysis. Numerische Mathematik, 116(1):123--148, 2010.

Digital Library

[19]

Y. Saad and M. H. Schultz. Gmres: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Stat. Comput., 7(3):856--869, July 1986.

Digital Library

[20]

O. Schenk and K. Gartner. Solving unsymmetric sparse systems of linear equations with {PARDISO}. Future Generation Computer Systems, 20(3):475--487, 2004. Selected numerical algorithms.

Digital Library

[21]

C. Wagner. Tangential frequency filtering decompositions for symmetric matrices. Numer. Math., 78(1):119--142, 1997.

Cited By

Thébault LPetit EDinh Q(2015)Scalable and efficient implementation of 3d unstructured meshes computation: a case study on matrix assemblyACM SIGPLAN Notices10.1145/2858788.268851750:8(120-129)Online publication date: 24-Jan-2015
https://dl.acm.org/doi/10.1145/2858788.2688517
Thébault LPetit EDinh QCohen AGrove D(2015)Scalable and efficient implementation of 3d unstructured meshes computation: a case study on matrix assemblyProceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/2688500.2688517(120-129)Online publication date: 24-Jan-2015
https://dl.acm.org/doi/10.1145/2688500.2688517
Grigori LNataf FQu L(2014)Overlapping for preconditioners based on incomplete factorizations and nested arrow formNumerical Linear Algebra with Applications10.1002/nla.193722:1(48-75)Online publication date: 19-May-2014
https://doi.org/10.1002/nla.1937

Parallel design and performance of nested filtering factorization preconditioner

Recommendations

Multi-threaded nested filtering factorization preconditioner
PARA'12: Proceedings of the 11th international conference on Applied Parallel and Scientific Computing

The scalability and robustness of a class of non-overlapping domain decomposition preconditioners using 2-way nested dissection reordering is studied. In particular, three methods are considered: a nested symmetric successive over-relaxation (NSSOR), a ...
Performance evaluation of a new parallel preconditioner
IPPS '95: Proceedings of the 9th International Symposium on Parallel Processing

The linear systems associated with large, sparse, symmetric, positive definite matrices are often solved iteratively using the preconditioned conjugate gradient method. We have developed a new class of preconditioners, support tree preconditioners, that ...
A Block FSAI-ILU Parallel Preconditioner for Symmetric Positive Definite Linear Systems

A novel parallel preconditioner for symmetric positive definite matrices is developed coupling a generalized factored sparse approximate inverse (FSAI) with an incomplete LU (ILU) factorization. The generalized FSAI, called block FSAI, is derived by ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SC '13: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis

November 2013

1123 pages

ISBN:9781450323789

DOI:10.1145/2503210

General Chair:
William Gropp
University of Illinois at Urbana-Champaign, Urbana, Illinois
,
Program Chair:
Satoshi Matsuoka
Tokyo Institute of Technology, Tokyo, Japan

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 November 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

Seventh Framework Programme

Conference

SC13

Sponsor:

SIGHPC
SIGARCH
IEEE-CS

SC13: International Conference for High Performance Computing, Networking, Storage and Analysis

November 17 - 21, 2013

Colorado, Denver

Acceptance Rates

SC '13 Paper Acceptance Rate 91 of 449 submissions, 20%;

Overall Acceptance Rate 1,516 of 6,373 submissions, 24%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
154
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)1

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Thébault LPetit EDinh Q(2015)Scalable and efficient implementation of 3d unstructured meshes computation: a case study on matrix assemblyACM SIGPLAN Notices10.1145/2858788.268851750:8(120-129)Online publication date: 24-Jan-2015
https://dl.acm.org/doi/10.1145/2858788.2688517
Thébault LPetit EDinh QCohen AGrove D(2015)Scalable and efficient implementation of 3d unstructured meshes computation: a case study on matrix assemblyProceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/2688500.2688517(120-129)Online publication date: 24-Jan-2015
https://dl.acm.org/doi/10.1145/2688500.2688517
Grigori LNataf FQu L(2014)Overlapping for preconditioners based on incomplete factorizations and nested arrow formNumerical Linear Algebra with Applications10.1002/nla.193722:1(48-75)Online publication date: 19-May-2014
https://doi.org/10.1002/nla.1937

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents