Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Sparse linear systems”

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 127 records · Page 7
All sourcesNASA NTRSDOE OSTI
NASA NTRS1984

Parallel triangularization of substructured finite element problems

Much of the computational effort of the finite element process involves the solution of a system of linear equations. The coefficient matrix of this system, known as the global stiffness matrix, is symmetric, positive definite, and generally sparse. An important technique for reducing the time required to solve this system is substructuring or matrix partitioning. Substructuring is based on the idea of dividing a structure into pieces, each of which can then be analyzed relatively indepenently. As a result of this division, each point in the finite element discretization is either interior to a substructure or on a boundary between substructures. Contributions to the global stiffness matrix from connections between boundary points from the K(bb) matrix are reported. The triangularization of a general K(bb) matrix on a parallel machine is specifically discussed.

Leuze, M. R.↗
DOE OSTI2021

Dynamics of disordered mechanical systems with large connectivity, free probability theory, and quasi-Hermitian random matrices

Disordered mechanical systems with high connectivity represent a limit opposite to the more familiar case of disordered crystals. Individual ions in a crystal are subjected essentially to nearest-neighbor interactions. In contrast, the systems studied in this paper have all their degrees of freedom coupled to each other. Thus, the problem of linearized small oscillations of such systems involves two full positive-definite and non-commuting matrices, as opposed to the sparse matrices associated with disordered crystals. Consequently, the familiar methods for determining the averaged vibrational spectra of disordered crystals, introduced many years ago by Dyson and Schmidt, are inapplicable for highly connected disordered systems. In this paper we apply random matrix theory (RMT) to calculate the averaged vibrational spectra of such systems, in the limit of infinitely large system size. At the heart of our analysis lies a calculation of the average spectrum of the product of two positive definite random matrices by means of free probability theory techniques. We also show that this problem is intimately related with quasi-hermitian random matrix theory (QHRMT), which means that the ‘hamiltonian’ matrix is hermitian with respect to a non-trivial metric. This extends ordinary hermitian matrices, for which the metric is simply the unit matrix. The analytical results we obtain for the spectrum agree well with our numerical results. The latter also exhibit oscillations at the high-frequency band edge, which fit well the Airy kernel pattern. We also compute inverse participation ratios of the corresponding amplitude eigenvectors and demonstrate that they are all extended, in contrast with conventional disordered crystals. Finally, we compute the thermodynamic properties of the system from its spectrum of vibrations. In addition to matrix model analysis, we also study the vibrational spectra of various multi-segmented disordered pendula, as concrete realizations of highly connected mechanical systems. A universal feature of the density of vibration modes, common to both pendula and the matrix model, is that it tends to a non-zero constant at vanishing frequency.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
NASA NTRS1985

Variation in efficiency of parallel algorithms

The present study has the objective to investigate some iterative parallel-processor linear equation solving algorithms with respect to efficiency for analyses of typical linear engineering systems. Attention is given to a set of n linear equations, Ku = p, where K = an n x n positive definite, sparsely populated, symmetric matrix, u = an n x 1 vector of unknown responses, and p = an n x 1 vector of prescribed constants. This study is concerned with a hybrid method in which iteration is used to solve the problem, while a direct method is used on the local processor level. Variations in the efficiency of parallel algorithms are explored. Measures of the efficiency are based on computer experiments regarding the algorithms. For all the algorithms, the wall clock time is found to decrease as the number of processors increases.

Hayashi, A.↗
DOE OSTI2023

Derivative-based SINDy (DSINDy): Addressing the challenge of discovering governing equations from noisy data

Recent advances in the field of data-driven dynamics allow for the discovery of ODE systems using state measurements. One approach, known as Sparse Identification of Nonlinear Dynamics (SINDy), assumes the dynamics are sparse within a predetermined basis in the states and finds the expansion coefficients through linear regression with sparsity constraints. This approach requires an accurate estimation of the state time derivatives, which is not necessarily possible in the high-noise regime without additional constraints. We present an approach called Derivative-based SINDy (DSINDy) that combines two novel methods to improve ODE recovery at high-noise levels. First, we denoise the state variables by applying a projection operator that leverages the assumed basis for the system dynamics. Second, we use a second order cone program (SOCP) to find the derivative and governing equations simultaneously. We derive theoretical results for the projection-based denoising step, which allow us to estimate the values of hyperparameters used in the SOCP formulation. This underlying theory helps limit the number of required user-specified parameters. Finally, we present results demonstrating that our approach leads to improved system recovery for the Van der Pol oscillator, the Duffing oscillator, the Rössler attractor, and the Lorenz 96 model.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

Block encoding bosons by signal processing

Block Encoding (BE) is a crucial subroutine in many modern quantum algorithms, including those with near-optimal scaling for simulating quantum many-body systems, which often rely on Quantum Signal Processing (QSP). Currently, the primary methods for constructing BEs are the Linear Combination of Unitaries (LCU) and the sparse oracle approach. In this work, we demonstrate that QSP-based techniques, such as Quantum Singular Value Transformation (QSVT) and Quantum Eigenvalue Transformation for Unitary Matrices (QETU), can themselves be efficiently utilized for BE implementation. Specifically, we present several examples of using QSVT and QETU algorithms, along with their combinations, to block encode Hamiltonians for lattice bosons, an essential ingredient in simulations of high-energy physics. We also introduce a straightforward approach to BE based on the exact implementation of Linear Operators Via Exponentiation and LCU (LOVE-LCU). We find that, while using QSVT for BE results in the best asymptotic gate count scaling with the number of qubits per site, LOVE-LCU outperforms all other methods for operators acting on up to qubits, highlighting the importance of concrete circuit constructions over mere comparisons of asymptotic scalings. Using LOVE-LCU to implement the BE, we simulate the time evolution of single-site and two-site systems in the lattice theory using the Generalized QSP algorithm and compare the gate counts to those required for Trotter simulation.

Kane, Christopher F↗
DOE OSTI2025

RE-INTEGRATE EMT Simulation Software: Graph Convolutional Network for Sparse Matrix Pattern Detection

The increasing complexity of power networks, driven by proliferation of inverters, presents analytical challenges that simplified models often fail to capture, necessitating Electromagnetic Transient (EMT) simulations. EMT models are represented as discretized differential-algebraic equations (DAEs), forming a linear system Ax = b that is computationally intensive to solve. Due to inherent sparsity of adjacency matrix A, distinct patterns emerge that, when accurately identified, enable efficient solver selection to minimize computation time. However, identifying ideal pattern is complicated by numerous reordering algorithms and limited structural insights. To address this, we introduce a Graph Convolutional Network (GCN) model for classifying sparse matrix patterns common in power system analysis. The model, achieving 96% test accuracy, is validated using PV plant models of 125 MW capacities connected to New England 39-bus transmission system (TS), and further scaled to a 4,992-bus network with 384 PV plants, yielding 191, 616 × 191, 616 sized A matrix. For all cases, the GCN model accurately identifies the matrix’s intrinsic sparse pattern, demonstrating its potential to enhance solver performance in EMT analysis.

Hossain, Md Rifat [Florida International Universit↗
DOE OSTI2026

Domain Knowledge Guided Bayesian Optimization For Autonomous Alignment Of Complex Scientific Instruments

Bayesian Optimization (BO) is a powerful tool for optimizing complex non-linear systems. However, its performance degrades in high-dimensional problems with tightly coupled parameters and highly asymmetric objective landscapes, where rewards are sparse. In such needle-in-a-haystack scenarios, even advanced methods like trust-region BO (TurBO) often lead to unsatisfactory results. We propose a domain knowledge guided Bayesian Optimization approach, which leverages physical insight to fundamentally simplify the search problem by transforming coordinates to decouple input features and align the active subspaces with the primary search axes. We demonstrate this approach's efficacy on a challenging 12-dimensional, 6-crystal Split-and-Delay optical system, where conventional approaches, including standard BO, TuRBO and multi-objective BO, consistently led to unsatisfactory results. When combined with an reverse annealing exploration strategy, this approach reliably converges to the global optimum. The coordinate transformation itself is the key to this success, significantly accelerating the search by aligning input co-ordinate axes with the problem's active subspaces. As increasingly complex scientific instruments, from large telescopes to new spectrometers at X-ray Free Electron Lasers are deployed, the demand for robust high-dimensional optimization grows. Our results demonstrate a generalizable paradigm: leveraging physical insight to transform high-dimensional, coupled optimization problems into simpler representations can enable rapid and robust automated tuning for consistent high performance while still retaining current optimization algorithms.

FOS: Computer and information sciences↗
NASA NTRS1988

Newton solution of inviscid and viscous problems

The application of Newton iteration to inviscid and viscous airfoil calculations is examined. Spatial discretization is performed using upwind differences with split fluxes. The system of linear equations which arises as a result of linearization in time is solved directly using either a banded matrix solver or a sparse matrix solver. In the latter case, the solver is used in conjunction with the nested dissection strategy, whose implementation for airfoil calculations is discussed. The boundary conditions are also implemented in a fully implicit manner, thus yielding quadratic convergence. Complexities such as the ordering of cell nodes and the use of a far field vortex to correct freestream for a lifting airfoil are addressed. Various methods to accelerate convergence and improve computational efficiency while using Newton iteration are discussed. Results are presented for inviscid, transonic nonlifting and lifting airfoils and also for laminar viscous cases.

Venkatakrishnan, V.↗
NASA NTRS1989

Krylov methods preconditioned with incompletely factored matrices on the CM-2

The performance is measured of the components of the key interative kernel of a preconditioned Krylov space interative linear system solver. In some sense, these numbers can be regarded as best case timings for these kernels. Sweeps were timed over meshes, sparse triangular solves, and inner products on a large 3-D model problem over a cube shaped domain discretized with a seven point template. The performance of the CM-2 is highly dependent on the use of very specialized programs. These programs mapped a regular problem domain onto the processor topology in a careful manner and used the optimized local NEWS communications network. The rather dramatic deterioration in performance was documented when these ideal conditions no longer apply. A synthetic workload generator was developed to produce and solve a parameterized family of increasingly irregular problems.

Berryman, Harry↗
NASA NTRS1989

Numerical methods in Markov chain modeling

Several methods for computing stationary probability distributions of Markov chains are described and compared. The main linear algebra problem consists of computing an eigenvector of a sparse, usually nonsymmetric, matrix associated with a known eigenvalue. It can also be cast as a problem of solving a homogeneous singular linear system. Several methods based on combinations of Krylov subspace techniques are presented. The performance of these methods on some realistic problems are compared.

Philippe, Bernard↗
DOE OSTI2025

Predicting Flow in Fracture Networks With Quantum Algorithms

Uncertainty quantification plays a crucial role in the modeling of subsurface flow. For instance, uncertainties in the properties of geologic fracture networks significantly impact flow, requiring numerous simulations to accurately estimate quantities of interest. However, each simulation is computationally expensive because it requires solving a large linear system to capture features that involve both small and large fractures. An example is in percolation, where the interaction of many small fractures (which cumulatively can have a large surface area) with the rock matrix must be modeled precisely. Quantum computing is an emerging tool with the potential to address this issue. Quantum algorithms offer a significant speedup in solving linear systems, achieving efficiencies that are challenging to match with classical approaches. These classical approaches include direct solvers, such as LU decomposition, and iterative methods, notably preconditioned conjugate gradient, commonly used in subsurface modeling to solve large sparse systems. However, applying quantum algorithms to geologic fracture flow requires careful attention to algorithmic and problem-specific constraints to fully realize this quantum advantage. In this work we describe a quantum algorithm for generalized Monte Carlo applications with a quadratic speedup over the classical approaches which can be combined with the quantum speedup, currently under investigation, for solving quantum linear systems for subsurface flow. We show that for quantum algorithms the computational cost of estimating a quantity of interest for a statistical ensemble of networks is roughly the same as that of a single realization, essentially implying that one can get uncertainty quantification for free.

58 GEOSCIENCES↗
NASA NTRS1976

SPAR reference manual

The functions and operating rules of the SPAR system, which is a group of computer programs used primarily to perform stress, buckling, and vibrational analyses of linear finite element systems, were given. The following subject areas were discussed: basic information, structure definition, format system matrix processors, utility programs, static solutions, stresses, sparse matrix eigensolver, dynamic response, graphics, and substructure processors.

Whetstone, W. D.↗
NASA NTRS2000

Ordering Unstructured Meshes for Sparse Matrix Computations on Leading Parallel Systems

The ability of computers to solve hitherto intractable problems and simulate complex processes using mathematical models makes them an indispensable part of modern science and engineering. Computer simulations of large-scale realistic applications usually require solving a set of non-linear partial differential equations (PDES) over a finite region. For example, one thrust area in the DOE Grand Challenge projects is to design future accelerators such as the SpaHation Neutron Source (SNS). Our colleagues at SLAC need to model complex RFQ cavities with large aspect ratios. Unstructured grids are currently used to resolve the small features in a large computational domain; dynamic mesh adaptation will be added in the future for additional efficiency. The PDEs for electromagnetics are discretized by the FEM method, which leads to a generalized eigenvalue problem Kx = AMx, where K and M are the stiffness and mass matrices, and are very sparse. In a typical cavity model, the number of degrees of freedom is about one million. For such large eigenproblems, direct solution techniques quickly reach the memory limits. Instead, the most widely-used methods are Krylov subspace methods, such as Lanczos or Jacobi-Davidson. In all the Krylov-based algorithms, sparse matrix-vector multiplication (SPMV) must be performed repeatedly. Therefore, the efficiency of SPMV usually determines the eigensolver speed. SPMV is also one of the most heavily used kernels in large-scale numerical simulations.

Oliker, Leonid↗
NASA NTRS1978

Structural performance analysis and redesign

Program performs stress buckling and vibrational analysis of large, linear, finite-element systems in excess of 50,000 degrees of freedom. Cost, execution time, and storage requirements are kept reasonable through use of sparse matrix solution techniques, and other computational and data management procedures designed for problems of very large size.

Whetstone, W. D.↗
NASA NTRS2009

Estimation of Faults in DC Electrical Power System

This paper demonstrates a novel optimization-based approach to estimating fault states in a DC power system. Potential faults changing the circuit topology are included along with faulty measurements. Our approach can be considered as a relaxation of the mixed estimation problem. We develop a linear model of the circuit and pose a convex problem for estimating the faults and other hidden states. A sparse fault vector solution is computed by using 11 regularization. The solution is computed reliably and efficiently, and gives accurate diagnostics on the faults. We demonstrate a real-time implementation of the approach for an instrumented electrical power system testbed, the ADAPT testbed at NASA ARC. The estimates are computed in milliseconds on a PC. The approach performs well despite unmodeled transients and other modeling uncertainties present in the system.

Gorinevsky, Dimitry↗
DOE OSTI2024

Parallel interior-point solver for block-structured nonlinear programs on SIMD/GPU architectures

Here, we investigate how to port the standard interior-point method to new exascale architectures for block-structured nonlinear programs with state equations. Computationally, we decompose the interior-point algorithm into two successive operations: the evaluation of the derivatives and the solution of the associated Karush-Kuhn-Tucker (KKT) linear system. Our method accelerates both operations using two levels of parallelism. First, we distribute the computations on multiple processes using coarse parallelism. Second, each process uses SIMD/GPU accelerators locally to accelerate the operations using fine-grained parallelism. The KKT system is reduced by eliminating the inequalities and the state variables from the corresponding equations. We demonstrate our method's capability on the supercomputer Polaris, a testbed for the future exascale Aurora system. Each node is equipped with four GPUs, a setup amenable to our two-level approach. Our experiments on the stochastic optimal power flow problem show that the reduction method is 50x faster than the sparse linear solver HSL MA57 running in serial on the CPU, and 6x faster than Pardiso running in parallel on CPU on the same number of processes.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1977

SPAR: Structural-performance analysis and redesign

System of processor programs performs stress, buckling, and vibrational analysis of large linear finite element systems in excess of 50,000 degrees of freedom, while minimizing processing cost, execution time, central memory storage, and secondary data storage requirements. Programs use sparse matrix solution techniques and other computational and data management procedures.

Whetstone, W. D.↗
NASA NTRS1994

Tensor-GMRES method for large sparse systems of nonlinear equations

This paper introduces a tensor-Krylov method, the tensor-GMRES method, for large sparse systems of nonlinear equations. This method is a coupling of tensor model formation and solution techniques for nonlinear equations with Krylov subspace projection techniques for unsymmetric systems of linear equations. Traditional tensor methods for nonlinear equations are based on a quadratic model of the nonlinear function, a standard linear model augmented by a simple second order term. These methods are shown to be significantly more efficient than standard methods both on nonsingular problems and on problems where the Jacobian matrix at the solution is singular. A major disadvantage of the traditional tensor methods is that the solution of the tensor model requires the factorization of the Jacobian matrix, which may not be suitable for problems where the Jacobian matrix is large and has a 'bad' sparsity structure for an efficient factorization. We overcome this difficulty by forming and solving the tensor model using an extension of a Newton-GMRES scheme. Like traditional tensor methods, we show that the new tensor method has significant computational advantages over the analogous Newton counterpart. Consistent with Krylov subspace based methods, the new tensor method does not depend on the factorization of the Jacobian matrix. As a matter of fact, the Jacobian matrix is never needed explicitly.

Feng, Dan↗