MueLu User's Guide for Trilinos Version 11.12

Manual text content

SANDIA REPORT SAND2014-18874 Unlimited Release Printed October 2014 MueLu User’s Guide for Trilinos Version 11.12 Andrey Prokopenko, Jonathan J. Hu, Tobias A. Wiesner, Christopher M. Siefert, Raymond S. Tuminaro Prepared by Sandia National Laboratories Albuquerque, New Mexico 87185 and Livermore, California 94550 Sandia National Laboratories is a multi-program laboratory managed and operated by Sandia Corporation, a wholly owned subsidiary of Lockheed Martin Corporation, for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-AC04-94AL85000. Approved for public release; further dissemination unlimited. Issued by Sandia National Laboratories, operated for the United States Department of Energy by Sandia Corporation. NOTICE: This report was prepared as an account of work sponsored by an agency of the United States Government. Neither the United States Government, nor any agency thereof, nor any of their employees, nor any of their contractors, subcontractors, or their employees, make any warranty, express or implied, or assume any legal liability or responsibility for the accuracy, completeness, or usefulness of any information, apparatus, product, or process disclosed, or rep- resent that its use would not infringe privately owned rights. Reference herein to any specific commercial product, process, or service by trade name, trademark, manufacturer, or otherwise, does not necessarily constitute or imply its endorsement, recommendation, or favoring by the United States Government, any agency thereof, or any of their contractors or subcontractors. The views and opinions expressed herein do not necessarily state or reflect those of the United States Government, any agency thereof, or any of their contractors. Printed in the United States of America. This report has been reproduced directly from the best available copy. Available to DOE and DOE contractors from U.S. Department of Energy Office of Scientific and Technical Information P.O. Box 62 Oak Ridge, TN 37831 Telephone: (865) 576-8401 Facsimile: (865) 576-5728 E-Mail: reports@adonis.osti.gov Online ordering: http://www.osti.gov/bridge Available to the public from U.S. Department of Commerce National Technical Information Service 5285 Port Royal Rd Springfield, VA 22161 Telephone: (800) 553-6847 Facsimile: (703) 605-6900 E-Mail: orders@ntis.fedworld.gov Online ordering: http://www.ntis.gov/help/ordermethods.asp?loc=7-4-0#online D E P A R T M E N T O F E N E R G Y • • U N I T E D S T A T E S O F A M E R I C A 2 SAND2014-18874 Unlimited Release Printed October 2014 MueLu User’s Guide for Trilinos Version 11.12 Andrey Prokopenko Scalable Algorithms Sandia National Laboratories Mailstop 1318 P.O. Box 5800 Albuquerque, NM 87185-1318 aprokop@sandia.gov Tobias Wiesner Institute for Computational Mechanics Technische Universit¨ at M¨ unchen Boltzmanstraße 15 85747 Garching, Germany wiesner@lnm.mw.tum.de Jonathan J. Hu Scalable Algorithms Sandia National Laboratories Mailstop 9159 P.O. Box 0969 Livermore, CA 94551-0969 jhu@sandia.gov Christopher M. Siefert Computational Multiphysics Sandia National Laboratories Mailstop 1322 P.O. Box 5800 Albuquerque, NM 87185-1322 csiefer@sandia.gov Raymond S. Tuminaro Computational Mathematics Sandia National Laboratories Mailstop 9159 P.O. Box 0969 Livermore, CA 94551-0969 rstumin@sandia.gov 3 Abstract This is the official user guide for the M UE L U multigrid library in Trilinos version 11.12. This guide provides an overview of M UE L U , its capabilities, and instructions for new users who want to start using M UE L U with a minimum of effort. Detailed information is given on how to drive M UE L U through its XML interface. Links to more advanced use cases are given. This guide gives information on how to achieve good parallel performance, as well as how to introduce new algorithms. Finally, readers will find a comprehensive listing of available M UE L U options. Any options not documented in this manual should be considered strictly experimental. 4 Acknowledgment Many people have helped develop M UE L U and/or provided valuable feedback, and we would like to acknowledge their contributions here: Tom Benson, Julian Cortial, Stefan Domino, Travis Fisher, Jeremie Gaidamour, Axel Gerstenberger, Chetan Jhurani, Mark Hoemmen, Jonathan Hu, Paul Lin, Eric Phipps, Andrey Prokopenko, Siva Rajamanickam, Chris Siefert, Paul Tsuji, Ray Tuminaro, and Tobias Wiesner. 5 6 Contents 1 Introduction 11 2 Getting Started 13 2.1 Prerequisites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Overview of M UE L U . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3 Quick Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.4 Multigrid Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.5 Configuring and Building . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.5.1 Required Dependencies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.5.2 Recommended Dependencies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.5.3 Tutorial Dependencies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.5.4 Complete List of Direct Dependencies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.5.5 Configuring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.6 Simple Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.6.1 M UE L U as preconditioner within B ELOS . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.6.2 M UE L U as preconditioner within A ZTEC OO . . . . . . . . . . . . . . . . . . . . . . . 20 2.6.3 Further remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3 Performance tips 23 3.1 Tips for impatient user . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4 M UE L U options 25 4.1 Using parameters on individual levels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 7 4.2 Parameter validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.3 General options . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.4 Smoothing and coarse solver options . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.5 Aggregation options . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.6 Rebalancing options . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.7 Multigrid algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.8 Miscellaneous options . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 References 33 8 List of Figures 2.1 High level multigrid V cycle consisting of ‘Nlevel’ levels to solve Ax = b , with A 0 = A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 9 List of Tables 2.1 M UE L U ’s required and optional dependencies. Dependencies are further subdi- vided by whether the M UE L U library itself has a dependency ( Library ), or whether a M UE L U test has a dependency ( Testing ). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.1 Commonly used smoothers provided by I FPACK /I FPACK 2. Note that these smoothers can also be used as coarse grid solvers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.2 Commonly used direct solvers provided by A MESOS /A MESOS 2 . . . . . . . . . . . . . . . 27 4.3 Available coarsening schemes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 10 Chapter 1 Introduction This guide is gives an overview of M UE L U ’s capabilities. If you are looking for a tutorial, please refer to the M UE L U tutorial in muelu/doc/Tutorial . New users should start with § 2. It strives to give the new user all the information he/she might need to begin using M UE L U quickly. Those who are interested in optimizing parallel performance should refer to section § 3. Users who simply need to look up particular options should refer to the complete set of supported options is given in § 4. Power users or developers who are interested in extending M UE L U should read § ?? , which describes how M UE L U can be modified to incorporate new algorithms. If you find errors or omissions in this guide, please contact the M UE L U developer list, muelu-developers@ software.sandia.gov . 11 12 Chapter 2 Getting Started This section is meant to get you using M UE L U as quickly as possible. 2.1 Prerequisites It’s assumed the reader is comfortable with T EUCHOS referenced-counted pointers (RCPs) for memory management. An introduction to RCPs can be found in [3]. This guide also assumes familiarity with the Teuchos::ParameterList class [11]. 2.2 Overview of M UE L U M UE L U is an extensible multigrid library that is part of the T RILINOS project. M UE L U works with E PETRA (32- and 64-bit versions) and T PETRA matrix types. The library is written in C++ and allows for different ordinal (index) and scalar types. M UE L U is designed to be efficient on many different computer architectures, from workstations to supercomputers. While it is MPI based, M UE L U is relies on the “MPI+X” principle, where “X” can be threading or CUDA. M UE L U provides a number of different multigrid algorithms: 1. smoothed aggregation algebraic multigrid (AMG), appropriate for Poisson-like and elasticity problems 2. Petrov-Galerkin aggregation AMG for convection-diffusion problems 3. aggregation-based AMG for problems arising from the eddy current formulation of Maxwell’s equations M UE L U ’s software design allows for the rapid introduction of new multigrid algorithms. 13 2.3 Quick Start The M UE L U C++ interface works with either E PETRA or T PETRA matrices. Solver options can be provided either by XML input files or parameter lists (key/value pairs). In this example for T PETRA users, options are read from an XML text file. 1 Teuchos::RCP<Tpetra::CrsMatrix<> > A; 2 // create A here ... 3 Teuchos::RCP<MueLu::TpetraOperator> mueLuPreconditioner; 4 std::string optionsFile = "mueluOptions.xml"; 5 mueLuPreconditioner = MueLu::CreateTpetraPreconditioner(A, optionsFile); A similar interface exists for E PETRA users. 1 Teuchos::RCP<Epetra_CrsMatrix> A; 2 // create A here ... 3 Teuchos::RCP<MueLu::EpetraOperator> mueLuPreconditioner; 4 std::string optionsFile = "mueluOptions.xml"; 5 mueLuPreconditioner = MueLu::CreateEpetraPreconditioner(A, optionsFile); In this example for T PETRA users, options are provided via a Teuchos::ParameterList . 1 Tpetra::CrsMatrix<> A; 2 // create A here ... 3 Teuchos::RCP<MueLu::TpetraOperator> mueLuPreconditioner; 4 Teuchos::ParameterList paramList; 5 paramList.set("verbosity", "medium"); 6 paramList.set("multigrid algorithm", "sa"); 7 paramList.set("aggregation: type", "uncoupled"); 8 paramList.set("smoother: type", "CHEBYSHEV"); 9 paramList.set("coarse: max size", 500); 10 mueLuPreconditioner = MueLu::CreateTpetraPreconditioner(A, paramList); 2.4 Multigrid Introduction A brief multigrid description is given here (see [5] or [12] for more information). A multigrid solver tries to approximate the original problem of interest with a sequence of smaller ( coarser ) problems. The solutions from the coarser problems are interpolated and combined in order to accelerate convergence of the original ( fine ) problem. on the finest grid. A simple multilevel iteration is illustrated in Figure 2.1. (This algorithm is borrowed from [8].) In the multigrid iteration in Figure 2.1, the S 1 k () ’s and S 2 k () ’s are called pre-smoothers and post-smoothers . They are approximate solvers (e.g. symmetric Gauss-Seidel), and the subscript k 14 function M ULTILEVEL ( A k , b , u , k ) // Solve A k u = b (k is current grid level) u = S 1 k ( A k , b , u ) if ( k 6 = Nlevel − 1 ) then P k = determine interpolant( A k ) ˆ r = P T k ( b − A k u ) ˆ A k + 1 = P T k A k P k v = 0 multilevel( ˆ A k + 1 , ˆ r , v , k + 1) u = u + P k v u = S 2 k ( A k , b , u ) end if end function Figure 2.1. High level multigrid V cycle consisting of ‘Nlevel’ levels to solve Ax = b , with A 0 = A . denotes the number of applications of the approximate solution method. The purpose of a smoother is to quickly reduce certain error modes in the approximate solution on a level i . For symmetric fine level problems, the pre- and post-smoothers must be chosen to maintain symmetry (e.g., for- ward Gauss-Seidel for the pre-smoother and backward Gauss-Seidel for the post-smoother). For the coarsest level, often a direct solve is employed if the problem is small enough. The P k ’s are interpolation matrices that transfer solutions from coarse levels to finer levels. In geometric multi- grid, the P k ’s are determined by the application, whereas they are automatically generated in an algebraic multigrid method. For symmetric problems, typically R k = P T k . For nonsymmetric prob- lems, this is not necessarily true. The A k ’s are the coarse level problems and are generated through a so-called Galerkin product. Note that the algebraic multigrid algorithms implemented in M UE L U generate the grid transfers P k automatically and the coarse problems A k via a sparse triple matrix product. There are many smoothers and direct solvers available for use in M UE L U through the I FPACK , I FPACK 2, A MESOS , and A MESOS 2 packages (see § 4). 2.5 Configuring and Building M UE L U has been compiled successfully with GNU (many 4.x versions), Intel 12.1/13.1 and clang 3.4 C++ compilers. 15 2.5.1 Required Dependencies M UE L U requires that T EUCHOS and either E PETRA /I FPACK or T PETRA /I FPACK 2 be enabled. 2.5.2 Recommended Dependencies We strongly recommend that you enable the following dependencies along with M UE L U : • E PETRA stack: A ZTEC OO, E PETRA , A MESOS , I FPACK , I SORROPIA , G ALERI , Z OLTAN • T PETRA stack: A MESOS 2, B ELOS , G ALERI , I FPACK 2, T PETRA , Z OLTAN 2 2.5.3 Tutorial Dependencies In order to run the M UE L U Tutorial [13] located in muelu/doc/Tutorial , M UE L U must be configured with the following dependencies enabled: A ZTEC OO, A MESOS , A MESOS 2, B ELOS , E PETRA , I FPACK , I FPACK 2, I SORROPIA , G ALERI , T PETRA , Z OLTAN , Z OLTAN 2. 2.5.4 Complete List of Direct Dependencies Table 2.1 enumerates the dependencies of M UE L U . Certain dependencies are optional, whereas others are required. Furthermore, M UE L U ’s tests depend on certain libraries that are not required if you only want to link against the M UE L U library and do not want to compile its tests. A MESOS 2 is necessary if you want to use a sparse direct solve on the coarsest level. Z OLTAN 2 is necessary if you want to be able to rebalance a matrix in parallel (see § 3). B ELOS is necessary if you want to be able to use M UE L U as a preconditioner instead of a solver. * Note that M UE L U has also been successfully tested with SuperLU 4.1 and SuperLU 4.2. * Be aware that other packages such as Z OLTAN and Z OLTAN 2 may come with additional require- ments for third party libraries (such as ParMetis), which are not listed here as explicit dependencies of M UE L U . It is highly recommended to install ParMetis 3.1.1 or newer for Z OLTAN and ParMetis 4.0.x for Z OLTAN 2. 2.5.5 Configuring You should configure and build M UE L U in a directory other than the source tree. Here we give a sample configure script that will enable M UE L U and all of its optional dependencies: 16 Dependency Required Optional Library Testing Library Testing A MESOS x x A MESOS 2 x x A ZTEC OO x B ELOS x E PETRA x x I FPACK x x I FPACK 2 x x I SORROPIA x x G ALERI x K OKKOS C LASSIC x T EUCHOS x x T PETRA x x X PETRA x x Z OLTAN x x Z OLTAN 2 x x Boost x BLAS x x LAPACK x x MPI x x SuperLU 4.3 x x Table 2.1. M UE L U ’s required and optional dependencies. De- pendencies are further subdivided by whether the M UE L U library itself has a dependency ( Library ), or whether a M UE L U test has a dependency ( Testing ). 17 export TRILINOS_HOME=/path/to/your/Trilinos/source/directory cmake -D BUILD_SHARED_LIBS:BOOL=ON \ -D CMAKE_BUILD_TYPE:STRING="RELEASE" \ -D CMAKE_CXX_FLAGS:STRING="-g" \ -D Trilinos_ENABLE_EXPLICIT_INSTANTIATION:BOOL=ON \ -D Trilinos_ENABLE_TESTS:BOOL=OFF \ -D Trilinos_ENABLE_EXAMPLES:BOOL=OFF \ -D Trilinos_ENABLE_MueLu:BOOL=ON \ -D MueLu_ENABLE_TESTS:STRING=ON \ -D MueLu_ENABLE_EXAMPLES:STRING=ON \ -D TPL_ENABLE_BLAS:BOOL=ON \ -D TPL_ENABLE_MPI:BOOL=ON \ ${TRILINOS_HOME} More configure examples can be found in Trilinos/sampleScripts . For more information on configuring, see the Trilinos quick start guide [1]. 2.6 Simple Example The most common scenario for M UE L U is that the user needs an iterative linear solver with an AMG preconditioner. When using T RILINOS the user has the choice between T PETRA and E PETRA for the underlying linear algebra. For linear solvers T RILINOS provides the packages A ZTEC OO and B ELOS which both implement the most important iterative Krylov subspace meth- ods such as CG and GMRES. 2.6.1 M UE L U as preconditioner within B ELOS Assuming that T PETRA is used for the linear algebra with a linear solver from the B ELOS package the following code shows the basic steps how to use a M UE L U multigrid preconditioner. The focus is on the algorithmic outline of setting up a linear solver, such that we skip the template parameters to keep the example short and clear. The user may refer to the corresponding source files within the examples and test folders for concrete examples. First we create the M UE L U multigrid preconditioner using xml parameters from a file on the hard disk (e.g., mueluOptions.xml in the example below). 1 Teuchos::RCP<Tpetra::CrsMatrix<> > A; 2 // create A here ... 3 Teuchos::RCP<MueLu::TpetraOperator> mueLuPreconditioner; 4 std::string optionsFile = "mueluOptions.xml"; 5 mueLuPreconditioner = MueLu::CreateTpetraPreconditioner(A, optionsFile); 18 The xml file defines the multigrid preconditioner. A typical parameter list file for M UE L U looks like 1 <ParameterList name="MueLu"> 2 3 <Parameter name="verbosity" type="string" value="low"/> 4 5 <Parameter name="max levels" type="int" value="3"/> 6 <Parameter name="coarse: max size" type="int" value="10"/> 7 8 <Parameter name="multigrid algorithm" type="string" value="sa"/> 9 10 <!-- Smoothing --> 11 <!-- Comment/uncomment different sections to try different smoothers --> 12 13 <!-- Jacobi --> 14 <Parameter name="smoother: type" type="string" value="RELAXATION"/> 15 <ParameterList name="smoother: params"> 16 <Parameter name="relaxation: type" type="string" value="Jacobi"/> 17 <Parameter name="relaxation: sweeps" type="int" value="1"/> 18 <Parameter name="relaxation: damping factor" type="double" value="0.9"/> 19 </ParameterList> 20 21 <!-- Aggregation --> 22 <Parameter name="aggregation: type" type="string" value="uncoupled"/> 23 <Parameter name="aggregation: min agg size" type="int" value="3"/> 24 <Parameter name="aggregation: max agg size" type="int" value="9"/> 25 26 </ParameterList> It defines a 3 level smoothed aggregation multigrid algorithm (optimal for symmetric positive definite matrices). The aggregation size is between 3 and 9 nodes which may be a good choice for a 2D problem. As level smoother one sweep with a damped Jacobi method is used. On the coarsest level a direct solver is applied per default. A complete list of all available parameters and valid parameter choices is given in § 4 of this user guide. Beside of the linear operator A we als need an initial guess vector for the solution and a right hand side vector for solving a linear system 1 Teuchos::RCP<const Tpetra::Map<> > map = A->getDomainMap(); 2 3 // Create initial vectors 4 Teuchos::RCP<Tpetra::MultiVector<> > B, X; 5 X = Teuchos::rcp( new Tpetra::MultiVector<>(map,numrhs) ); 6 Belos::MultiVecTraits<>::MvRandom( *X ); 7 B = Teuchos::rcp( new Tpetra::MultiVector<>(map,numrhs) ); 8 Belos::OperatorTraits<>::Apply( *A, *X, *B ); 9 Belos::MultiVecTraits<>::MvInit( *X, 0.0 ); 19 To generate a dummy example above code first declares to vectors. The right hand side vector is calculated as matrix vector product of a random vector with the operator A . The initial guess is finally initialized with zeros. Then, one can define a Belos::LinearProblem object where the mueLuPreconditioner is used for left preconditioning. 1 Belos::LinearProblem<> problem( A, X, B ); 2 problem->setLeftPrec(mueLuPreconditioner); 3 bool set = problem.setProblem(); Next, we can set up a B ELOS solver using some basic parameters 1 Teuchos::ParameterList belosList; 2 belosList.set( "Block Size", 1 ); 3 belosList.set( "Maximum Iterations", 100 ); 4 belosList.set( "Convergence Tolerance", 1e-10 ); 5 belosList.set( "Output Frequency", 1 ); 6 belosList.set( "Verbosity", Belos::TimingDetails + Belos::FinalSummary ); 7 8 Belos::BlockCGSolMgr<> solver( rcp(&problem,false), rcp(&belosList,false) ); Finally, one can perform the solution process using 1 Belos::ReturnType ret = solver.solve(); 2.6.2 M UE L U as preconditioner within A ZTEC OO When using E PETRA the A ZTEC OO is an alternative for B ELOS which provides fast and ma- ture implementations of iterative linear solvers (even though the user is recommended to use the more modern B ELOS implementations). Assuming that the linear operator is given as an E PETRA object the M UE L U preconditioner can be generated via 1 Teuchos::RCP<Epetra_CrsMatrix> A; 2 // create A here ... 3 Teuchos::RCP<MueLu::EpetraOperator> mueLuPreconditioner; 4 std::string optionsFile = "mueluOptions.xml"; 5 mueLuPreconditioner = MueLu::CreateEpetraPreconditioner(A, optionsFile); The file format for the xml parameter file is the same as for the example from § 2.6.1. Furthermore, we assume that a right hand side vector and a solution vector with the initial guess are defined 20 1 Teuchos::RCP<const Epetra_Map> map = A->DomainMap(); 2 Teuchos::RCP<Epetra_Vector> B = Teuchos::rcp(new Epetra_Vector(map)); 3 Teuchos::RCP<Epetra_Vector> X = Teuchos::rcp(new Epetra_Vector(map)); 4 X->PutScalar(0.0); Then, a Epetra LinearProblem can be defined by 1 Epetra_LinearProblem epetraProblem(A.get(), X.get(), B.get()); With the following lines an A ZTEC OO CG solver is generated 1 AztecOO aztecSolver(epetraProblem); 2 aztecSolver.SetAztecOption(AZ_solver, AZ_cg); 3 aztecSolver.SetPrecOperator(mueLuPreconditioner.get()); Finally, the linear system is solved via 1 int maxIts = 100; 2 double tol = 1e-10; 3 aztecSolver.Iterate(maxIts, tol); 2.6.3 Further remarks This section is only meant to give a rough overview on how to use M UE L U as preconditioner within the T RILINOS packages for iterative solvers. There are other more complicated ways to use M UE L U as preconditioners for B ELOS and A ZTEC OO through the X PETRA interface. Of course, M UE L U can also work as standalone multigrid solver. For more information on these topics with examples the reader may refer to the examples and tests in the M UE L U source folder as well as to the M UE L U tutorial ([13]). 21 22 Chapter 3 Performance tips This Section gives few tips on tuning M UE L U performance. 3.1 Tips for impatient user 1. Use matrix rebalancing options when running in parallel. See § ?? . 2. Adjust aggregation strategy. See § ?? . 3. Try replacing direct solver with a few smoothing steps, if coarse level solve becomes too expensive. See § 4.6. 4. Choose a smoother whose computational kernel is a matvec, such as the Chebyshev polyno- mial smoother, if a problem is symmetric positive definite. See § 4.4. 23 24 Chapter 4 M UE L U options In this section, we report the complete list of M UE L U input parameters. It is important to notice, however, that M UE L U relies on other T RILINOS packages to provide support for some of its algorithms. For instance, I FPACK /I FPACK 2 provide standard smoothers like Jacobi, Gauss- Seidel or Chebyshev, while A MESOS /A MESOS 2 provide access to direct solvers. The parameters affecting the behaviour of delegated algorithms are simply passed by M UE L U to a routine from the corresponding package. Please consult corresponding packages for a full list of supported algorithms and corresponding parameters. 4.1 Using parameters on individual levels Some of the parameters that affect the preconditioner can in principle be different from level to level. By default, parameters affects all levels in the multigrid hierarchy. The settings on a particular levels can be changed by using level sublists. Level sublist is a ParameterList sublist with a name “level XX”. The parameter names in the sublist do not require any modifications. For example, the following fragment of code <ParameterList name="level 2"> <Parameter name="smoother: type" type="string" value="CHEBYSHEV"/> </ParameterList> changes the smoother for level 2 to be a polynomial smoother. 4.2 Parameter validation By default, M UE L U validates the input parameter list. A parameter that is misspelled or un- known, or has an incorrect value type will cause an exception to be thrown and execution to halt. * Spaces are important within a parameter’s name. Please separate words by just one space, and make sure there are no leading or trailing spaces. 25 The option print initial parameters prints the initial list given to the interpreter. The option print unused parameters prints the list of unused parameters. 4.3 General options verbosity [ s tring] Control of the amount of printed information. Possible values: ”none”, ”low”, ”medium”, ”high”, ”extreme”. Default: ”high”. number of equations [ i nt] Number of PDE equations at each gride node. Only constant block size is considered. Default: 1. max levels [ i nt] Maximum number of levels. Default: 10. cycle type [ s tring] Multigrid cycle type. Possible values: ”V”, ”W”. Default: ”V”. problem: symmetric [ b ool] Symmetry of a problem. Default: true. 4.4 Smoothing and coarse solver options M UE L U relies on other T RILINOS packages to provide level smoothers and coarse solvers. I FPACK and I FPACK 2 provide standard smoothers (see Table 4.1), and A MESOS and A MESOS 2 provide direct solvers (see Table 4.2). Note that it is completely possible to use any level smoother as a direct solver. M UE L U checks parameters smoother: * type and coarse: type to determine: • what package to use (i.e., is it a smoother or direct solver); • possibly transform the type (in case of a smoother) * I FPACK and I FPACK 2 use different types to construct smoothers (e.g., “point relaxation stand-alone” vs “RELAXATION”). M UE L U follows I FPACK 2 notation for smoother types. Please consult I FPACK 2 manual [10]. 26 The parameter lists smoother: * params and coarse: params are passed directly to the corre- sponding package without any examination of their content. Please consult corresponding manuals for a list of possible values. By default, M UE L U uses one sweep of symmetric Gauss-Seidel for both pre- and post-smoothing, and SuperLU for coarse system solver. smoother: type RELAXATION Point relaxation smoothers, including Jacobi, Gauss-Seidel, symmetric Gauss-Seidel, etc. The exact smoother is cho- sen by specifying relaxation: type parameter in the smoother: params sublist. CHEBYSHEV Chebyshev polynomial smoother. ILUT , RILUK Local (processor-based) incomplete factorization methods. Table 4.1. Commonly used smoothers provided by I F - PACK /I FPACK 2. Note that these smoothers can also be used as coarse grid solvers. coarse: type A MESOS A MESOS 2 KLU x Default A MESOS solver [7]. KLU2 x Default A MESOS 2 solver [4]. SuperLU x x Third-party serial sparse direct solver [9]. SuperLU_dist x x Third-party parallel sparse direct solver [9]. Umfpack x Third-party solver [6]. Mumps x Third-party solver [2]. Table 4.2. Commonly used direct solvers provided by A ME - SOS /A MESOS 2 smoother: pre or post [ s tring] Smoother combination. Possible values: ”pre”, ”post”, ”both”, ”none”. Default: ”both”. smoother: type [ s tring] Smoother type. Possible values: see Table 4.1. Default: one sweep of symmetric Gauss-Seidel. 27 smoother: pre type [ s tring] Pre-smoother type. Possible values: see Ta- ble 4.1. Default: one sweep of symmetric Gauss- Seidel. smoother: post type [ s tring] Post-smoother type. Possible values: see Ta- ble 4.1. Default: one sweep of symmetric Gauss- Seidel. smoother: params [ ParameterList ] Smoother parameters. For standard smoothers, M UE L U passes them directly to S TRA - TIMIKOS . smoother: pre params [ ParameterList ] Pre-smoother parameters. For stan- dard smoothers, M UE L U passes them directly to S TRATIMIKOS . smoother: post params [ ParameterList ] Post-smoother parameters. For standard smoothers, M UE L U passes them directly to S TRATIMIKOS . smoother: overlap [ i nt] Smoother subdomain overlap. Default: 0. smoother: pre overlap [ i nt] Pre-smoother subdomain overlap. Default: 0. smoother: post overlap [ i nt] Post-smoother subdomain overlap. Default: 0. coarse: max size [ i nt] Maximum dimension of the coarse grid. M UE L U will stop coarsening once it is achieved. Default: 2000. coarse: type [ s tring] Coarse solver. Possible values: see Table 4.2. Default: ”SuperLU”. coarse: params [ ParameterList ] Coarse solver parameters. M UE L U passes them directly to coarse solver. coarse: overlap [ i nt] Coarse solver subdomain overlap. Default: 0. 28 4.5 Aggregation options uncoupled Attempts to construct aggregates of optimal size (3 d nodes in d dimensions). Each process works independently, and aggregates cannot span processes. coupled Attempts to construct aggregates of optimal size (3 d nodes in d dimensions). Aggregates are allowed to cross proces- sor boundaries. Use carefully. If unsure use uncoupled instead. Table 4.3. Available coarsening schemes. aggregation: type [ s tring] Aggregation scheme. Possible values: ”uncou- pled”, ”coupled”. Default: ”uncoupled”. aggregation: ordering [ s tring] Ordering strategy. Possible values: ”natrual”, ”graph”, ”random”. Default: ”natural”. aggregation: drop scheme [ s tring] Aggregation connectivity dropping scheme. Possible values: ”classical”, ”distance laplacian”. De- fault: ”classical”. aggregation: drop tol [ d ouble] Aggregation dropping threshold. De- fault: 0.0. aggregation: min agg size [ i nt] Minimum size of an aggregate. Default: 2. aggregation: max agg size [ i nt] Maximum size of an aggregate. De- fault: 2147483647. aggregation: Dirichlet threshold [ d ouble] Threshold for determining whether entries are zero during Dirichlet row detection. Default: 0.0. aggregation: export visualization data [ b ool] Export data for visualization post-processing. Default: false. 29 4.6 Rebalancing options repartition: enable [ b ool] Repartitioning on/off switch. Default: false. repartition: partitioner [ s tring] Partitioning package to use. Possible values: ”zoltan”, ”zoltan2”. Default: ”zoltan2”. repartition: params [ ParameterList ] Partitioner parameters. M UE L U passes them directly to partitioner. repartition: start level [ i nt] Minimum level to run partitioner. M UE L U does not repartition for finer levels. Default: 2. repartition: min rows per proc [ i nt] Desired minimum number of rows per processor. If actual number if smaller, then repartitioning occurs. Default: 800. repartition: max imbalance [ d ouble] Desired maximum nonzero imbalance ratio. Default: 1.2. repartition: remap parts [ b ool] Postprocessing for partitioning to reduce data migration. Default: true. repartition: rebalance P and R [ b ool] Do rebalancing of R and P during the setup. This speeds up the solve, but slows down the setup phases. Default: true. 4.7 Multigrid algorithms multigrid algorithm [ s tring] Multigrid method. Possible values: ”un- smoothed”, ”sa”, ”emin”, ”pg”. Default: ”sa”. 30 semicoarsen: coarsen rate [ i nt] Rate at which to coarsen unknowns in the z direc- tion. Default: 3. sa: damping factor [ d ouble] Damping factor for smoothed aggregation. Default: 1.33333333. sa: use filtered matrix [ b ool] Matrix to use for smoothing the tentative prolon- gator. The two options are: to use the original matrix, and to use the filtered matrix with filtering based on fil- tered graph used for aggregation. Default: true. filtered matrix: use lumping [ b ool] During construction of a filtered matrix, we have an option to add dropped entries to the diagonal. This is useful for preserving constant nullspace for the Lapla- cian type matrix. Default: true. filtered matrix: reuse eigenvalue [ b ool] During construction of a filtered matrix, we have an option to get the eigenvalue estimate from the orig- inal matrix. This allows us to skip heavy computation. Default: true. emin: iterative method [ s tring] Iterative method to use for energy minimiza- tion of intial prolongator in energy-minimization. Pos- sible values: ”cg”, ”sd”. Default: ”cg”. emin: num iterations [ i nt] Number of iterations to minimize initial prolon- gator energy in energy-minimization. Default: 2. emin: num reuse iterations [ i nt] Number of iterations to minimize the reused pro- longator energy in energy-minimization. Default: 1. emin: pattern [ s tring] Sparsity pattern to use for energy minization. Possible values: ”AkPtent”. Default: ”AkPtent”. emin: pattern order [ i nt] Matrix order for the ”AkPtent” pattern. De- fault: 1. 31 4.8 Miscellaneous options export data [ ParameterList ] Exporting a subset of the hierarchy data in a file. Currently, the list can contain any of three parameter names (”A”, ”P”, ”R”) of type ”string” and value ” { levels separated by commas } ”. A matrix is saved in two files: a) data is saved in the MatrixMar- ket format in a file called ”A level.mm”, or similar; b) row map is saved in the MatrixMarket format in a file called ”rowmap A level.mm”, or similar. print initial parameters [ b ool] Print parameters provided for a hierarchy con- struction. Default: true. print unused parameters [ b ool] Print parameters unused during a hierarchy con- struction. Default: true. transpose: use implicit [ b ool] Use implicit transpose for the restriction opera- tor. Default: false. 32 References [1] Trilinos cmake quickstart. http://trilinos.org/build_instructions.html , 2014. [2] Patrick R Amestoy, Iain S Duff, Jean-Yves LExcellent, and Jacko Koster. Mumps: a general purpose distributed memory sparse solver. In Applied Parallel Computing. New Paradigms for HPC in Industry and Academia , pages 121–130. Springer, 2001. [3] Roscoe A Bartlett. Teuchos:: RCP beginners guide. Technical Report SAND2004-3268, Sandia National Labs, 2010. [4] Eric Bavier, Mark Hoemmen, Sivasankaran Rajamanickam, and Heidi Thornquist. Amesos2 and belos: Direct and iterative solvers for large sparse linear systems. Scientific Program- ming , 20(3):241–255, 2012. [5] William L Briggs, Steve F McCormick, et al. A multigrid tutorial . SIAM, 2nd edition, 2000. [6] Timothy A Davis. Algorithm 832: Umfpack v4. 3—an unsymmetric-pattern multifrontal method. ACM Transactions on Mathematical Software (TOMS) , 30(2):196–199, 2004. [7] Timothy A Davis and Ekanathan Palamadai Natarajan. Algorithm 907: Klu, a direct sparse solver for circuit simulation problems. ACM Transactions on Mathematical Software (TOMS) , 37(3):36, 2010. [8] M.W. Gee, C.M. Siefert, J.J. Hu, R.S. Tuminaro, and M.G. Sala. ML 5.0 smoothed aggrega- tion user’s guide. Technical Report SAND2006-2649, Sandia National Laboratories, 2006. [9] Xiaoye S. Li, James W. Demmel, John R. Gilbert, Laura Grigori, Meiyue Shao, and Ichitaro Yamazaki. SuperLU Users’ Guide. 2011. [10] Christopher Siefert and Jonathan Hu. Ifpack2 Users Guide. Technical report, Sandia National Labs, 2014. [11] Heidi Thornquist, Ross Bartlett, Mark Hoemmen, Christopher Baker, and Michael Heroux. Teuchos: Trilinos tools library. http://trilinos.org/packages/teuchos , 2014. [12] Ulrich Trottenberg, Cornelis Oosterlee, and Anton Schuller. Multigrid . Elsevier Academic Press, 2001. [13] Tobias A. Wiesner, Michael W. Gee, Andrey Prokopenko, and Jonathan Hu. The MueLu tutorial. http://trilinos.org/packages/muelu , 2014. SAND2014-18624R. 33 DISTRIBUTION: 1 Tobias Wiesner Institute for Computational Mechanics Technische Universit¨ at M¨ unchen Boltzmanstraße 15 85747 Garching, Germany 1 MS 1320 Michael Heroux, 1446 1 MS 1318 Robert Hoekstra, 1446 1 MS 1320 Mark Hoemmen, 1446 1 MS 1320 Paul Lin, 1446 1 MS 1318 Andrey Prokopenko, 1426 1 MS 1322 Christopher Siefert, 1443 1 MS 0899 Technical Library, 9536 (electronic copy) 34 DISTRIBUTION: 1 MS 9159 Jonathan Hu, 1426 1 MS 9159 Paul Tsuji, 1442 1 MS 9159 Raymond Tuminaro, 1442 1 MS 0899 Technical Library, 8944 (electronic copy) 35 36 v1.39