Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “preconditioning”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 703 records · Page 39

Conditioning Analysis of Incomplete Cholesky Factorizations with Orthogonal Dropping

The analysis of preconditioners based on incomplete Cholesky factorization in which the neglected (dropped) components are orthogonal to the approximations being kept is presented. General estimate for the condition number of the preconditioned system is given which only depends on the accuracy of individual approximations. The estimate is further improved if, for instance, only the newly computed rows of the factor are modified during each approximation step. In this latter case it is further shown to be sharp. The analysis is illustrated with some existing factorizations in the context of discretized elliptic partial differential equations.

97 MATHEMATICS AND COMPUTING↗

Monolithic multigrid methods for two-dimensional resistive magnetohydrodynamics

Magnetohydrodynamic (MHD) representations are used to model a wide range of plasma physics applications and are characterized by a nonlinear system of partial differential equations that strongly couples a charged fluid with the evolution of electromagnetic fields. The resulting linear systems that arise from discretization and linearization of the nonlinear problem are generally difficult to solve. In this paper, we investigate multigrid preconditioners for this system. We consider two well-known multigrid relaxation methods for incompressible fluid dynamics: Braess--Sarazin relaxation and Vanka relaxation. We first extend these to the context of steady-state one-fluid viscoresistive MHD. Then we compare the two relaxation procedures within a multigrid-preconditioned GMRES method employed within Newton's method. To isolate the effects of the different relaxation methods, we use structured grids, inf-sup stable finite elements, and geometric interpolation. Furthermore, we present convergence and timing results for a two-dimensional, steady-state test problem.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

An Algebraic Multilevel Preconditioner with Low-Rank Corrections for Sparse Symmetric Matrices

In this work, we describe a multilevel preconditioning technique for solving sparse symmetric linear systems of equations. This “Multilevel Schur Low-Rank” (MSLR) preconditioner first builds a tree structure $\mathcal{T}$ based on a hierarchical decomposition of the matrix and then computes an approximate inverse of the original matrix level by level. Unlike classical direct solvers, the construction of the MSLR preconditioner follows a top-down traversal of $\mathcal{T}$ and exploits a low-rank property that is satisfied by the difference between the inverses of the local Schur complements and specific blocks of the original matrix. A few steps of the generalized Lanczos tridiagonalization procedure are applied to capture most of this difference. Numerical results are reported to illustrate the efficiency and robustness of the MSLR preconditioner with both two- and three-dimensional discretized PDE problems and with publicly available test problems.

97 MATHEMATICS AND COMPUTING↗

Hybrid Multiscale Finite Volume Method for Advection-Diffusion Equations Subject to Heterogeneous Reactive Boundary Conditions

We present a hybrid scheme for the coupling of macro and microscale continuum models for reactive contaminant transport in fractured and porous media. The transport model considered is the advection-dispersion equation, subject to linear heterogeneous reactive boundary conditions. The Multiscale Finite Volume method (MsFV) is employed to define an approximation to the microscale concentration field defined in terms of macroscopic or \emph{global} degrees of freedom, together with local interpolator and corrector functions capturing microscopic spatial variability. The macroscopic mass balance relations for the MsFV global degrees of freedom are coupled with the macroscopic model, resulting in a global problem for the simultaneous time-stepping of all macroscopic degrees of freedom throughout the domain. In order to perform the hybrid coupling, the micro and macroscale models are applied over overlapping subdomains of the simulation domain, with the overlap denoted as the handshake subdomain $\Omega^{hs}$, over which continuity of concentration and transport fluxes between models is enforced. Continuity of concentration is enforced by posing a restriction relation between models over $\Omega^{hs}$. Continuity of fluxes is enforced by prolongating the macroscopic model fluxes across the boundary of $\Omega^{hs}$ to microscopic resolution. The microscopic interpolator and corrector functions are solutions to local microscopic advection-diffusion problems decoupled from the global degrees of freedom and from each other by virtue of the MsFV decoupling ansatz. The error introduced by the decoupling ansatz is reduced iteratively by the preconditioned GMRES algorithm, with the hybrid MsFV operator serving as the preconditioner.

Barajas-Solano, David A.↗

A Scalable Preconditioner for a Primal Discontinuous Petrov--Galerkin Method

In this work, we show how a scalable preconditioner for the primal discontinuous Petrov--Galerkin (DPG) method can be developed using existing algebraic multigrid (AMG) preconditioning techniques. The stability of the DPG method gives a norm equivalence which allows us to exploit existing AMG algorithms and software. We show how these algebraic preconditioners can be applied directly to a Schur complement system arising from the DPG method. One of our intermediate results shows that a generic stable decomposition implies a stable decomposition for the Schur complement. This justifies the application of algebraic solvers directly to the interface degrees of freedom. Combining such results, we obtain the first massively scalable algebraic preconditioner for the DPG system.

97 MATHEMATICS AND COMPUTING↗

A Robust and Efficient Implementation of LOBPCG

Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG) is widely used to compute eigenvalues of large sparse symmetric matrices. The algorithm can suffer from numerical instability if it is not implemented with care. This is especially problematic when the number of eigenpairs to be computed is relatively large. In this paper we propose an improved basis selection strategy based on earlier work by Hetmaniuk and Lehoucq as well as a robust convergence criterion which is backward stable to enhance the robustness. Here, we also suggest several algorithmic optimizations that improve performance of practical LOBPCG implementations. Numerical examples confirm that our approach consistently and significantly outperforms previous competing approaches in both stability and speed.

97 MATHEMATICS AND COMPUTING↗

A Scalable Multigrid Reduction Framework for Multiphase Poromechanics of Heterogeneous Media

Simulation of multiphase poromechanics involves solving a multiphysics problem in which multiphase flow and transport are tightly coupled with the porous medium deformation. To capture this dynamic interplay, fully implicit methods, also known as monolithic approaches, are usually preferred. The main bottleneck of a monolithic approach is that it requires solution of large linear systems that result from the discretization and linearization of the governing balance equations. Because such systems are nonsymmetric, indefinite, and highly ill-conditioned, preconditioning is critical for fast convergence. Recently, most efforts in designing efficient preconditioners for multiphase poromechanics have been dominated by physics-based strategies. Current state-of-the-art “black-box” solvers such as algebraic multigrid (AMG) are ineffective because they cannot effectively capture the strong coupling between the mechanics and the flow subproblems, as well as the coupling inherent in the multiphase flow and transport process. In this work, we develop an algebraic framework based on multigrid reduction (MGR) that is suited for tightly coupled systems of PDEs. Using this framework, the decoupling between the equations is done algebraically through defining appropriate interpolation and restriction operators. One can then employ existing solvers for each of the decoupled blocks or design a new solver based on knowledge of the physics. We demonstrate the applicability of our framework when used as a “black-box” solver for multiphase poromechanics. Here, we show that the framework is flexible to accommodate a wide range of scenarios, as well as efficient and scalable for large problems.

97 MATHEMATICS AND COMPUTING↗

Tuning Multigrid Methods with Robust Optimization and Local Fourier Analysis

Local Fourier analysis is a useful tool for predicting and analyzing the performance of many efficient algorithms for the solution of discretized PDEs, such as multigrid and domain decomposition methods. The crucial aspect of local Fourier analysis is that it can be used to minimize an estimate of the spectral radius of a stationary iteration, or the condition number of a preconditioned system, in terms of a symbol representation of the algorithm. In practice, this is a “minimax” problem, minimizing with respect to solver parameters the appropriate measure of work, which involves maximizing over the Fourier frequency. Often, several algorithmic parameters may be determined by local Fourier analysis in order to obtain efficient algorithms. Analytical solutions to minimax problems are rarely possible beyond simple problems; the status quo in local Fourier analysis involves grid sampling, which is prohibitively expensive in high dimensions. In this paper, we propose and explore optimization algorithms to solve these problems efficiently. Finally, several examples, with known and unknown analytical solutions, are presented to show the effectiveness of these approaches.

97 MATHEMATICS AND COMPUTING↗

Large-Scale Optimization with Linear Equality Constraints Using Reduced Compact Representation

For optimization problems with linear equality constraints, we prove that the (1,1) block of the inverse KKT matrix remains unchanged when projected onto the nullspace of the constraint matrix. In this work, we develop reduced compact representations of the limited-memory inverse BFGS Hessian to compute search directions efficiently when the constraint Jacobian is sparse. Orthogonal projections are implemented by a sparse QR factorization or a preconditioned LSQR iteration. In numerical experiments two proposed trust-region algorithms improve in computation times, often significantly, compared to previous implementations of related algorithms and compared to IPOPT.

97 MATHEMATICS AND COMPUTING↗

Additive Polynomial Time Integrators, Part I: Framework and Fully Implicit-Explicit Collocation Methods

In this paper we generalize the polynomial time integration framework to additively partitioned initial value problems. The framework we present is general and enables the construction of many new families of additive integrators with arbitrary order-of-accuracy and varying degree of implicitness. In this first work, we focus on a new class of implicit-explicit polynomial block methods that are based on fully implicit Runge–Kutta methods with Radau nodes and that possess high stage order. Here, we show that the new fully implicit-explicit (FIMEX) integrators have improved stability compared to existing IMEX Runge–Kutta methods, while also being more computationally efficient due to recent developments in preconditioning techniques for solving the associated systems of nonlinear equations. For PDEs on periodic domains where the implicit component is trivial to invert, we will show how parallelization of the right-hand side evaluations can be exploited to obtain significant speedup compared to existing serial IMEX Runge–Kutta methods. For parallel (in space) finite element discretizations, the new methods can achieve orders of magnitude better accuracy than existing IMEX Runge–Kutta methods and/or achieve a given accuracy several times times faster in terms of computational runtime.

97 MATHEMATICS AND COMPUTING↗

An Efficient High-Order Solver for Diffusion Equations with Strong Anisotropy on Non-Anisotropy-Aligned Meshes

This paper concerns numerical solution of the diffusion equation with strong anisotropy on meshes not aligned with the anisotropic vector field. In order to resolve the numerical pollution for simulations on a non-anisotropy-aligned mesh and reduce the associated high computational cost we propose an effective preconditioner, extending our previous work. Similar to the anisotropy-aligned mesh case, we apply the auxiliary space preconditioning framework to design a preconditioner where a continuous finite element space is used as the auxiliary space for the discontinuous finite element space. The key component is an effective line smoother that can mitigate the high-frequency errors perpendicular to the magnetic field. We design a graph-based approach to find such a line smoother that is approximately perpendicular to the vector fields when the mesh does not align with the anisotropy. Finally, numerical experiments for several benchmark problems are presented, demonstrating the effectiveness and robustness of the proposed preconditioner when applied to Krylov iterative methods.

97 MATHEMATICS AND COMPUTING↗

Surrogate-Based Autotuning for Randomized Sketching Algorithms in Regression Problems

Algorithms from Randomized Numerical Linear Algebra (RandNLA) are known to be effective in handling high-dimensional computational problems, providing high-quality empirical performance as well as strong probabilistic guarantees. However, their practical application is complicated by the fact that the user needs to set various algorithm-specific tuning parameters which are different from those used in traditional NLA. This paper demonstrates how a surrogate-based autotuning approach can be used to address fundamental problems of parameter selection in RandNLA algorithms. In particular, we provide a detailed investigation of surrogate-based autotuning for sketch-and-precondition (SAP)-based randomized least squares methods, which have been one of the great success stories in modern RandNLA. Empirical results show that our surrogate-based autotuning approach can achieve near-optimal performance with much less tuning cost than a random search (up to about 7.6x fewer trials of different parameter configurations). Moreover, while our experiments focus on least squares, our results demonstrate a general-purpose autotuning pipeline applicable to any kind of RandNLA algorithm.

Cho, Younghyun↗

Parallel-in-Time Solution of Scalar Nonlinear Conservation Laws

Here, we consider the parallel-in-time solution of scalar nonlinear conservation laws in one spatial dimension. The equations are discretized in space with a conservative finite-volume method using weighted essentially nonoscillatory (WENO) reconstructions, and in time with high-order explicit Runge–Kutta methods. The solution of the global, discretized space-time problem is sought via a nonlinear iteration that uses a novel linearization strategy in cases of nondifferentiable equations. Under certain choices of discretization and algorithmic parameters, the nonlinear iteration coincides with Newton’s method, although, more generally, it is a preconditioned residual correction scheme. At each nonlinear iteration, the linearized problem takes the form of a certain discretization of a linear conservation law over the space-time domain in question. An approximate parallel-in-time solution of the linearized problem is computed with a single multigrid reduction-in-time (MGRIT) iteration; however, any other effective parallel-in-time method could be used in its place. The MGRIT iteration employs a novel coarse-grid operator that is a modified conservative semi-Lagrangian discretization and generalizes those we have developed previously for nonconservative scalar linear hyperbolic problems. Numerical tests are performed for the inviscid Burgers and Buckley–Leverett equations. For many test problems, the solver converges in just a handful of iterations with a convergence rate independent of mesh resolution, including problems with (interacting) shocks and rarefactions.

97 MATHEMATICS AND COMPUTING↗

Statistical interpretation of sterile neutrino oscillation searches at reactors

A considerable experimental effort is currently under way to test the persistent hints for oscillations due to an eV-scale sterile neutrino in the data of various reactor neutrino experiments. The assessment of the statistical significance of these hints is usually based on Wilks’ theorem, whereby the assumption is made that the log-likelihood is χ 2 -distributed. However, it is well known that the preconditions for the validity of Wilks’ theorem are not fulfilled for neutrino oscillation experiments. In this work we derive a simple asymptotic form of the actual distribution of the log-likelihood based on reinterpreting the problem as fitting white Gaussian noise. From this formalism we show that, even in the absence of a sterile neutrino, the expectation value for the maximum likelihood estimate of the mixing angle remains non-zero with attendant large values of the log-likelihood. Our analytical results are then confirmed by numerical simulations of a toy reactor experiment. Finally, we apply this framework to the data of the Neutrino-4 experiment and show that the null hypothesis of no-oscillation is rejected at the 2.6 σ level, compared to 3.2 σ obtained under the assumption that Wilks’ theorem applies.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Improved unconstrained energy functional method for eigensolvers in electronic structure calculations

This paper reports on the performance of a preconditioned conjugate gradient based iterative eigensolver using an unconstrained energy functional minimization scheme. In contrast to standard implementations, this scheme avoids an explicit reorthogonalization of the trial eigenvectors and becomes an attractive alternative for the solution of very large problems. The unconstrained formulation is implemented in the first-principles materials and chemistry CP2K code, which performs electronic structure calculations based on a density functional theory approximation to the solution of the many-body Schrödinger equation. We study the convergence of the unconstrained formulation, as well as its parallel scaling, on a Cray XC40 at the National Energy Research Scientific Computing Center (NERSC). The systems we use in our studies are bulk liquid water, a supramolecular catalyst gold(III)-complex, a bilayer of MoS2-WSe2 and a divacancy point defect in silicon, with the number of atoms ranging from 2,247 to 12,288. We show that the unconstrained formulation with an appropriate preconditioner has good convergence properties and scales well to 230k cores, roughly 38% of the full machine.

Del Ben, M↗

Tifpack v 1.0

A package for computing and applying algebraic preconditioners in the context of preconditioned iterative methods. It is related to the existing Ifpack package in Trilinos but provides support for template scalar and ordinal types and explicitly relies on Tpetra and Kokkos instead of Epetra. Algebraic preconditioners are used by iterative solvers as solution method in engineering and scientific applications, including nonlinear equation solving, time integration, sensitivity analysis, stability analysis, optimization, and uncertainty quantification.

Heroux, Michael↗

Teko v. 1.0

Teko is a C++ library for implementation of blocked and segregated preconditioners in the context of iterative solvers for linear systems. Capabilities for decomposing larger matrices into user defined sub blocks are also provided. Additional functionality for creating approximate inverse operators utilizing solver and preconditioning packages in the Trilinos framework has also been implemented. Teko's primary application is in multiphysics simulation environment where a decomposition of the linear system in to physically meaningful blocks can be utilized to enhance performance of an iterative solver. However, applicability may extend to other problem domains where matrices can be decomposed into meaningful blocks.

Cyr, Eric↗