A Matrix-Free Approach to Smoothed Aggregation Algebraic Multigrid.
Abstract not provided.
Harper, Graham↗
SEARCH · Engineering Papers
Results for “algebraic approach”
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.
U(1) fields from qubits: An approach via D-theory algebra
A new quantum link microstructure was proposed for the lattice quantum chromodynamics (QCD) Hamiltonian, replacing the Wilson gauge links with a bilinear of fermionic qubits, later generalized to D-theory. This formalism provides a general framework for building lattice field theory algorithms for quantum computing. We focus mostly on the simplest case of a quantum rotor for a single compact U(1) field. We also make some progress for non-Abelian setups, making it clear that the ideas developed in the U(1) case extend to other groups. These in turn are building blocks for 1 + 0 -dimensional ( 1 + 0 -D) matrix models, 1 + 1 -D sigma models and non-Abelian gauge theories in 2 + 1 and 3 + 1 dimensions. By introducing multiple flavors for the U(1) field, where the flavor symmetry is gauged, we can efficiently approach the infinite-dimensional Hilbert space of the quantum O(2) rotor with increasing flavors. The emphasis of the method is on preserving the symplectic algebra exchanging fermionic qubits by sigma matrices (or hard bosons) and developing a formal strategy capable of generalization to a SU ( 3 ) field for lattice QCD and other non-Abelian 1 + 1 -D sigma models or 3 + 1 -D gauge theories. For U(1), we discuss briefly the qubit algorithms for the study of the discrete 1 + 1 -D sine-Gordon equation. Published by the American Physical Society 2024
Astronomy & Astrophysics↗
Robust 3D multi-material hydrodynamics using discontinuous Galerkin methods
A high-order discontinuous Galerkin (DG) method is presented for nonequilibrium multi-material (m ≥ 2) flow with sharp interfaces. Material interfaces are reconstructed using the algebraic THINC approach, resulting in a sharp interface resolution. The system assumes stiff velocity relaxation and pressure nonequilibrium. The presented DG method uses Dubiner's orthogonal basis functions on tetrahedral elements. This results in a unique combination of sharp multimaterial interfaces and high-order accurate solutions in smooth single-material regions. A novel shock indicator based on the interface conservation condition is introduced to mark regions with discontinuities. Slope limiting techniques are applied only in these regions so that nonphysical oscillations are eliminated while maintaining high-order accuracy in smooth regions. A local projection is applied on the limited solution to ensure discrete closure law preservation. The effectiveness of this novel limiting strategy is demonstrated for complex three-dimensional multi-material problems, where robustness of the method is critical. The presented numerical problems demonstrate that more accurate and efficient multi-material solutions can be obtained by the DG method, as compared to second-order finite volume methods.
97 MATHEMATICS AND COMPUTING↗
EXAGRAPH: Graph and combinatorial methods for enabling exascale applications
Combinatorial algorithms in general and graph algorithms in particular play a critical enabling role in numerous scientific applications. However, the irregular memory access nature of these algorithms makes them one of the hardest algorithmic kernels to implement on parallel systems. With tens of billions of hardware threads and deep memory hierarchies, the exascale computing systems in particular pose extreme challenges in scaling graph algorithms. The codesign center on combinatorial algorithms, ExaGraph, was established to design and develop methods and techniques for efficient implementation of key combinatorial (graph) algorithms chosen from a diverse set of exascale applications. Algebraic and combinatorial methods have a complementary role in the advancement of computational science and engineering, including playing an enabling role on each other. In this paper, we survey the algorithmic and software development activities performed under the auspices of ExaGraph from both a combinatorial and an algebraic perspective. In particular, we detail our recent efforts in porting the algorithms to manycore accelerator (GPU) architectures. We also provide a brief survey of the applications that have benefited from the scalable implementations of different combinatorial algorithms to enable scientific discovery at scale. We believe that several applications will benefit from the algorithmic and software tools developed by the ExaGraph team.
97 MATHEMATICS AND COMPUTING↗
Spherical Parameter Estimation and MPDV Applications
A new algebraic least square approach is presented for estimating effective zero center for verification of MPDV(Multichannel Photon Doppler Velocimetry) probe designs. Unlike previous algebraic least square methods for spherical parameter estimation, the new method can be shown to be concise in mathematic formulations, easy of computations, invariant under rigid -body transformations, no need for numerical approximations, and precise in dealing with precise data.
97 MATHEMATICS AND COMPUTING↗
Generalized Bootstrap AMG and AIR-AMG for coupled PDE systems with a focus on spacetime discretizatoins
The Pennsylvania State University (“Subcontractor”) has worked on the design of new algebraic, parallel, multilevel methods that obtain the full space and time solution of systems of PDEs. In particular, the PI and his collaborators explored semi-intrusive approaches based on algebraic multigrid (AMG). The focus of the research has been on the development of these techniques for the Euler equations in 1d and 2d. The overall research focused on the development of adaptive AIR (approximate ideal restriction) AMG solvers for these problems. The PI also explored the use of smoothed aggregation and root-node energy-based AMG solvers for these problems.
97 MATHEMATICS AND COMPUTING↗
A Fast Algebraic Multigrid Solver and Accurate Discretization for Highly Anisotropic Heat Flux I: Open Field Lines
We present a novel solver technique for the anisotropic heat flux equation, aimed at the high level of anisotropy seen in magnetic confinement fusion plasmas. Such problems pose two major challenges: (i) discretization accuracy and (ii) efficient implicit linear solvers. We simultaneously address each of these challenges by constructing a new finite element discretization with excellent accuracy properties, tailored to a novel solver approach based on algebraic multigrid (AMG) methods designed for advective operators. We pose the problem in a mixed formulation, introducing the directional temperature gradient as an auxiliary variable. The temperature and auxiliary fields are discretized in a scalar discontinuous Galerkin space with upwinding principles used for discretizations of advection. We demonstrate the proposed discretization’s superior accuracy over other discretizations of anisotropic heat flux, achieving error 1000x smaller for anisotropy ratio of 10 9 , for closed field lines. The block matrix system is reordered and solved in an approach where the two advection operators are inverted using AMG solvers based on approximate ideal restriction, which is particularly efficient for upwind discontinuous Galerkin discretizations of advection. To ensure that the advection operators are nonsingular, in this paper we restrict ourselves to considering open (acyclic) magnetic field lines for the linear solvers. We demonstrate fast convergence of the proposed iterative solver in highly anisotropic regimes where other diffusion-based AMG methods fail.
97 MATHEMATICS AND COMPUTING↗
Theory of Trotter Error with Commutator Scaling
The Lie-Trotter formula, together with its higher-order generalizations, provides a simple approach to decomposing the exponential of a sum of operators. Despite significant effort, the error scaling of such product formulas remains poorly understood. We develop a theory of Trotter error that overcomes the limitations of truncating the Baker-Campbell-Hausdorff expansion. Our analysis directly exploits the commutativity of operator summands, producing tighter error bounds for both real- and imaginary-time evolutions. Whereas previous work achieves similar goals for systems with geometric locality or Lie-algebraic structure, our approach holds in general. We give a host of improved algorithms for digital quantum simulation and quantum Monte Carlo methods, nearly matching or even outperforming the best previous results. Our applications include: (i) a simulation of second-quantized plane-wave electronic structure, nearly matching the interaction-picture algorithm of Low and Wiebe; (ii) a simulation of $k$-local Hamiltonians almost with induced one-norm scaling, faster than the qubitization algorithm of Low and Chuang; (iii) a simulation of rapidly decaying power-law interactions, outperforming the Lieb-Robinson-based approach of Tran et al.; (iv) a hybrid simulation of clustered Hamiltonians, dramatically improving the result of Peng, Harrow, Ozols, and Wu; and (v) quantum Monte Carlo simulations of the transverse field Ising model and quantum ferromagnets, tightening previous analyses of Bravyi and Gosset. We obtain further speedups using the fact that product formulas can preserve the locality of the simulated system. Specifically, we show that local observables can be simulated with complexity independent of the system size for power-law interacting systems, which implies a Lieb-Robinson bound nearly matching a recent result of Tran et al. Our analysis reproduces known tight bounds for first- and second-order formulas. We further investigate the tightness of our bounds for higher-order formulas. For quantum simulation of a one-dimensional Heisenberg model with an even-odd ordering of terms, our result overestimates the complexity by only a factor of $5$. Our bound is also close to tight for power-law interactions and other orderings of terms. This suggests that our theory can accurately characterize Trotter error in terms of both the asymptotic scaling and the constant prefactor.
quantum computing, numerical analysis↗
Foams and KZ-equations in Rozansky-Witten theories
In this paper, we present a geometric description of foams, which are prevalent in topological quantum field theories (TQFTs) based on quantum algebra, and reciprocally explore the geometry of Rozansky-Witten (RW) theory from an algebraic perspective. This approach illuminates various aspects of decorated TQFTs via geometry of the target space X of RW theory. Through the formulation of the Knizhnik-Zamolodchikov (KZ) equation within this geometric framework, we derive the corresponding braiding and associator morphisms. We discuss applications where the target space of RW theory emerges as the Coulomb branch of a compactified 6d SCFT or Little String Theory, with the latter being particularly intriguing as it results in a compact X.
Gukov, Sergei [California Institute of Technology,↗
An Analog Preconditioner for Solving Linear Systems [Slides]
This presentation concludes in situ computation enables new approaches to linear algebra problems which can be both more effective and more efficient as compared to conventional digital systems. Preconditioning is well-suited to analog computation due to the tolerance for approximate solutions. When combined with prior work on in situ MVM for scientific computing, analog preconditioning can enable significant speedups for important linear algebra applications.
97 MATHEMATICS AND COMPUTING↗
Approximate Inverse Chain Preconditioner: Iteration Count Case Study for Spectral Support Solvers
As the growing availability of computational power slows, there has been an increasing reliance on algorithmic advances. However, faster algorithms alone will not necessarily bridge the gap in allowing computational scientists to study problems at the edge of scientific discovery in the next several decades. Often, it is necessary to simplify or precondition solvers to accelerate the study of large systems of linear equations commonly seen in a number of scientific fields. Preconditioning a problem to increase efficiency is often seen as the best approach; yet, preconditioners which are fast, smart, and efficient do not always exist. Following the progress of [1], we present a new preconditioner for symmetric diagonally dominant (SDD) systems of linear equations. These systems are common in certain PDEs, network science, and supervised learning among others. Based on spectral support graph theory, this new preconditioner builds off of the work of [2], computing and applying a V-cycle chain of approximate inverse matrices. This preconditioner approach is both algebraic in nature as well as hierarchically-constrained depending on the condition number of the system to be solved. Due to its generation of an Approximate Inverse Chain of matrices, we refer to this as the AIC preconditioner. We further accelerate the AIC preconditioner by utilizing precomputations to simplify setup and multiplications in the con-text of an iterative Krylov-subspace solver. While these iterative solvers can greatly reduce solution time, the number of iterations can grow large quickly in the absence of good preconditioners. Initial results for the AIC preconditioner have shown a very large reduction in iteration counts for SDD systems as compared to standard preconditioners such as Incomplete Cholesky (ICC) and Multigrid (MG). We further show significant reduction in iteration counts against the more advanced Combinatorial Multigrid (CMG) preconditioner. We have further developed no-fill sparsification techniques to ensure that the computational cost of applying the AIC preconditioner does not grow prohibitively large as the depth of the V-cycle grows for systems with larger condition numbers. Our numerical results have shown that these sparsifiers maintain the sparsity structure of our system while also displaying significant reductions in iteration counts.1 2
97 MATHEMATICS AND COMPUTING↗
Approximate Inverse Chain Preconditioner: Iteration Count Case Study for Spectral Support Solvers
As the growing availability of computational power slows, there has been an increasing reliance on algorithmic advances. However, faster algorithms alone will not necessarily bridge the gap in allowing computational scientists to study problems at the edge of scientific discovery in the next several decades. Often, it is necessary to simplify or precondition solvers to accelerate the study of large systems of linear equations commonly seen in a number of scientific fields. Preconditioning a problem to increase efficiency is often seen as the best approach; yet, preconditioners which are fast, smart, and efficient do not always exist. Following the progress of [1], we present a new preconditioner for symmetric diagonally dominant (SDD) systems of linear equations. These systems are common in certain PDEs, network science, and supervised learning among others. Based on spectral support graph theory, this new preconditioner builds off of the work of [2], computing and applying a V-cycle chain of approximate inverse matrices. This preconditioner approach is both algebraic in nature as well as hierarchically-constrained depending on the condition number of the system to be solved. Due to its generation of an Approximate Inverse Chain of matrices, we refer to this as the AIC preconditioner. We further accelerate the AIC preconditioner by utilizing precomputations to simplify setup and multiplications in the con-text of an iterative Krylov-subspace solver. While these iterative solvers can greatly reduce solution time, the number of iterations can grow large quickly in the absence of good preconditioners. Initial results for the AIC preconditioner have shown a very large reduction in iteration counts for SDD systems as compared to standard preconditioners such as Incomplete Cholesky (ICC) and Multigrid (MG). We further show significant reduction in iteration counts against the more advanced Combinatorial Multigrid (CMG) preconditioner. We have further developed no-fill sparsification techniques to ensure that the computational cost of applying the AIC preconditioner does not grow prohibitively large as the depth of the V-cycle grows for systems with larger condition numbers. Our numerical results have shown that these sparsifiers maintain the sparsity structure of our system while also displaying significant reductions in iteration counts.1 2
97 MATHEMATICS AND COMPUTING↗
A reduced space simultaneous approach for optimization of nonlinear index-1 differential algebraic equations.
Abstract not provided.
Parker, Robert↗
A reduced space simultaneous approach for optimization of nonlinear index-1 differential algebraic equations.
Abstract not provided.
Parker, Robert↗
Heavy-Duty Vehicle Air Drag Coefficient Estimation: From an Algebraic Perspective
When a heavy-duty vehicle (HDV) operates at the nominal highway speed, over two-thirds of its total resistive force comes from the air drag, contributing to more than half of its fuel consumption. One effective countermeasure to reduce the fuel consumption of HDVs is platooning, which employs connectivity and automated driving technologies to link two or more HDVs in convoy. Platooning allows HDVs to drive closer together and yields improved fuel economy and less CO2 emission thanks to the reduced air drag. Maximizing the energy benefits of an HDV platoon requires quantifying the drag interaction between vehicles. In practice, modeling the drag reduction in a platoon boils down to identifying the relationship between the air drag coefficient C d and the inter-vehicle distance d. Existing approaches to identify C d (d) include vehicle field tests, wind tunnel experiments, and computational fluid dynamics simulation, which can howbeit be time-consuming and cost prohibitive. In contrast, this paper proposes an algebraic approach, which relies on onboard-measurable variables, to estimate the air drag coefficient of an HDV in a platoon. Its algebraic nature avoids the classical persistence of excitation condition for parameter identification and can yield the identified parameter almost instantaneously. Simulation results demonstrate its effectiveness and the improved estimation speed over a recursive least squares identifier.
Wang, Zejiang↗
Non-intrusive data-driven model reduction for differential–algebraic equations derived from lifting transformations
In this paper we present a non-intrusive data-driven approach for model reduction of nonlinear systems. The approach considers the particular case of nonlinear partial differential equations (PDEs) that form systems of partial differential–algebraic equations (PDAEs) when lifted to polynomial form. Such systems arise, for example, when the governing equations include Arrhenius reaction terms (e.g., in reacting flow models) and thermodynamic terms (e.g., the Helmholtz free energy terms in a phase-field solidification model). Using the known structured form of the lifted algebraic equations, the approach computes the reduced operators for the algebraic equations explicitly, using straightforward linear algebra operations on the basis matrices. The reduced operators for the differential equations are inferred from lifted snapshot data using operator inference, which solves a linear least squares regression problem. The approach is illustrated for the nonlinear model of solidification of a pure material. The lifting transformations reformulate the solidification PDEs as a system of PDAEs that have cubic structure. The operators of the lifted system for this solidification example have affine dependence on key process parameters, permitting us to learn a parametric reduced model with operator inference. Numerical experiments show the effectiveness of the resulting reduced models in capturing key aspects of the solidification dynamics.
42 ENGINEERING↗
Adaptive Algebraic Derivative Estimation for Battery Electric Buses Energy Consumption Forecasting
The limited service life of onboard batteries for EVs is a challenge, underscoring the need for real-time battery usage prediction. This paper proposes an adaptive Algebraic Derivative Estimation (ADE) approach for forecasting the energy consumption of battery electric buses. By dynamically adjusting the sliding window length, the adaptive ADE retains the fixed-length ADE’s key advantage—namely, operating online without reliance on extensive historical datasets—while substantially bolstering forecast accuracy by actively trading estimation bias off estimation variance. Comparative experiments against both the conventional ADE with a fixed length and a representative machine learning algorithm, XGBoost, were conducted, with performance evaluated via root mean square error, mean absolute error, and the coefficient of determination. The results demonstrate that the proposed approach significantly outperforms baseline methods.
Cui, Tianyang [The University of Texas at Dallas]↗
Dynamic mode decomposition with core sketch
With the increase in collected data volumes, either from experimental measurements or high fidelity simulations, there is an ever-growing need to develop computationally efficient tools to process, analyze, and interpret these datasets. Modal analysis techniques have gained great interest due to their ability to identify patterns in the data and extract valuable information about the system being considered. Dynamic mode decomposition (DMD) relies on elements of the Koopman approximation theory to compute a set of modes, each associated with a fixed oscillation frequency and a decay/growth rate. Extracting these details from large datasets can be computationally expensive due to the need to implement singular value decomposition of the input data matrix. Sketching algorithms have become popular in numerical linear algebra where statistical theoretic approaches are utilized to reduce the cost of major operations. A sketch of a matrix is another matrix, which is significantly smaller, but still sufficiently approximates the original system. We put forth an efficient DMD framework, SketchyDMD, based on a core sketching algorithm that captures information about the range and corange (their mutual relationship) of input data. The proposed sketching-based framework can accelerate various portions of the DMD routines, compared to classical methods that operate directly on the raw input data. We conduct numerical experiments using the spherical shallow water equations as a prototypical model in the context of geophysical flows. In conclusion, we show that the proposed SketchyDMD is superior to existing randomized DMD methods that are based on capturing only the range of the input data.
71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗