Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “linear system”

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 55 records · Page 3

A Flexible CUDA LU-based Solver for Small, Batched Linear Systems

This chapter presents the implementation of a batched CUDA solver based on LU factorization for small linear systems. This solver may be used in applications such as reactive flow transport models, which apply the Newton-Raphson technique to linearize and iteratively solve the sets of non linear equations that represent the reactions for ten of thousands to millions of physical locations. The implementation exploits somewhat counterintuitive GPGPU programming techniques: it assigns the solution of a matrix (representing a system) to a single CUDA thread, does not exploit shared memory and employs dynamic memory allocation on the GPUs. These techniques enable our implementation to simultaneously solve sets of systems with over 100 equations and to employ LU decomposition with complete pivoting, providing the higher numerical accuracy required by certain applications. Other currently available solutions for batched linear solvers are limited by size and only support partial pivoting, although they may result faster in certain conditions. We discuss the code of our implementation and present a comparison with the other implementations, discussing the various tradeoffs in terms of performance and flexibility. This work will enable developers that need batched linear solvers to choose whichever implementation is more appropriate to the features and the requirements of their applications, and even to implement dynamic switching approaches that can choose the best implementation depending on the input data.

bached linear solvers↗

Linear and Nonlinear Solvers for Simulating Multiphase Flow within Large-Scale Engineered Subsurface Systems

Simulation of multiphase flow in the subsurface is well-known to be computationally challenging. While there have been many studies that have explored approaches to overcoming these challenges, they often utilize relatively simple case studies. In this paper, we focus on the unique numerical challenges posed by modeling large-scale engineered subsurface systems, characterized by discrete features embedded in a heterogeneous natural subsurface setting. The man-made features such as shafts, tunnels, and barriers often cause multiple challenges in modeling the domain for multiphase porous media flow. This flow scenario can have a wide range of applications such as nuclear waste repositories, enhanced recovery of a petroleum reservoir, geothermal engineering, and carbon sequestration. An example of these severe numerical challenges is the case of performance assessment (PA) for Waste Isolation Pilot Plant (WIPP), the only operating deep geological repository in the US, which simulates extreme material properties of bedded salt rock formation and extreme contrast due to open excavation next to the formation. The models have extremes not only of permeability and porosity but also of the constitutive models needed for multiphase flow; additionally, they have process models like salt creep closure reducing porosity over time, fracturing in clay and anhydrite interbeds of the bedded salt, gas generation from the waste materials, and unintentional human borehole intrusions in some scenarios. Numerical simulations require the solution of coupled systems of nonlinear PDEs; in our work, we use the open-source simulator PFLOTRAN which is based on Finite Volume discretization. The solution of the nonlinear equations requires use of the Newton-Raphson iteration at each time step, which entails the solution of the linearized Jacobian system at each iteration. The effects of all the processes (i.e., large number of unknowns, highly nonlinear constitutive relations, large contrasts in material properties in short distances) lead to an ill-conditioned Jacobian matrix that severely challenges traditional linear solver, i.e., stabilized biconjugate gradient with block Jacobi incomplete LU preconditioner (BCGS-ILU) leading to non-convergence for traditional Newton-Raphson nonlinear solver causing unacceptably long computation time for each model. This paper presents linear solvers such as constrained pressure residual (CPR) two-stage preconditioner with alternate-block-factorization (ABF) and quasi- implicit pressure and explicit saturation (QIMPES) decouplers and flexible generalized residual solver (FGMRES). The new general-purpose nonlinear solver, Newton trust-region dogleg Cauchy (NTRDC), is also introduced to resolve extreme nonlinearities in the models. We demonstrate the effectiveness of each method relative to the default BCGS-Newton solver. The two best cases had nearly 50 times speed-up and achieved completion of a simulation in 14 hours that never completed due to non-convergence with the default solver. We also investigate the strong scalability of each method and discuss some of the deficiencies found for Block Jacobi preconditioner using parallel domain decomposition, and node packing effects of modern processor architecture.

Preconditioner, Nonlinear, Porous media, Multiphas↗

Penalized ensemble Kalman filters for high dimensional non-linear systems

The ensemble Kalman filter (EnKF) is a data assimilation technique that uses an ensemble of models, updated with data, to track the time evolution of a usually non-linear system. It does so by using an empirical approximation to the well-known Kalman filter. However, its performance can suffer when the ensemble size is smaller than the state space, as is often necessary for computationally burdensome models. This scenario means that the empirical estimate of the state covariance is not full rank and possibly quite noisy. To solve this problem in this high dimensional regime, we propose a computationally fast and easy to implement algorithm called the penalized ensemble Kalman filter (PEnKF). Under certain conditions, it can be theoretically proven that the PEnKF will be accurate (the estimation error will converge to zero) despite having fewer ensemble members than state dimensions. Further, as contrasted to localization methods, the proposed approach learns the covariance structure associated with the dynamical system. These theoretical results are supported with simulations of several non-linear and high dimensional systems.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

On the Stability of a Linear System of Difference Equations with Random Parameters

We study the asymptotic behavior of solutions to a linear system of difference equation whose right-hand side at each time moment depends not only on the value at the previous moment, but also on a random parameter that takes its values in a given set. We obtain conditions of the Lyapunov stability and the asymptotic stability of the equilibrium position that are valid for all values of the random parameter or with probability 1.

97 MATHEMATICS AND COMPUTING↗

On Stability of Linear Systems with Impulsive Action at the Matrix

We discuss properties of stability and asymptotic stability of solutions to linear systems of differential equations with generalized actions in matrices of systems. We obtain sufficient conditions that guarantee the stability and asymptotic stability of solutions to these system. A distinctive feature of systems considered is the fact that the right-hand sides of systems contain the ill-posed operation of multiplication of discontinuous functions by generalized functions.

97 MATHEMATICS AND COMPUTING↗

Stability of linear systems in second-order form based on structure preserving similarity transformations

This paper deals with two stability aspects of linear systems of the form I ¨ x +B˙ x +Cx = 0 given by the triple (I;B;C). A general transformation scheme is given for a structure and Jordan form preserving transformation of the triple. We investigate how a system can be transformed by suitable choices of the transformation parameters into a new system (I;B1;C1) with a symmetrizable matrix C1. This procedure facilitates stability investigations. We also consider systems with a Hamiltonian spectrum which discloses marginal stability after a Jordan form preserving transformation.

Stoustrup, Jakob↗

Optimal-Order Preconditioners for Linear Systems Arising in the Semismooth Newton Solution of a Class of Control-Constrained Problems

We present a new multigrid preconditioner for the linear systems arising in the semismooth Newton method solution of certain control-constrained, quadratic distributed optimal control problems. Using a piecewise constant discretization of the control space, each semismooth Newton iteration essentially requires inverting a principal submatrix of the matrix entering the normal equations of the associated unconstrained optimal control problem, the rows (and columns) of the submatrix representing the constraints deemed inactive at the current iteration. Previously developed multigrid preconditioners for the aforementioned submatrices were based on constructing a sequence of conforming coarser spaces and proved to be of suboptimal quality for the class of problems considered. Instead, the multigrid preconditioner introduced in this work uses nonconforming coarse spaces, and it is shown that, under reasonable geometric assumptions on the constraints that are deemed inactive, the preconditioner approximates the inverse of the desired submatrix to optimal order. The preconditioner is tested numerically on a classical elliptic-constrained optimal control problem and further on a constrained image-deblurring problem.

97 MATHEMATICS AND COMPUTING↗

SU-E-I-11: Cascaded Linear System Model for Columnar CsI Flat Panel Imagers with Depth Dependent Gain and Blur

Purpose: To implement a depth dependent gain and blur cascaded linear system model (CLSM) for optimizing columnar structured CsI indirect conversion flat panel imager (FPI) for advanced imaging applications. Methods: For experimental validation, depth dependent escape efficiency, e(z), was extracted from PHS measurement of different CsI scintillators (thickness, substrate and light output). The inherent MTF and DQE of CsI was measured using high resolution CMOS sensor. For CLSM, e(z) and the depth dependent MTF(f,z), were estimated using Monte Carlo simulation (Geant4) of optical photon transport through columnar CsI. Previous work showed that Monte Carlo simulation for CsI was hindered by the non-ideality of its columnar structure. In the present work we allowed variation in columnar width with depth, and assumed diffusive reflective backing and columns. Monte Carlo simulation was performed using an optical point source placed at different depth of the CsI layer, from which MTF(z,f) and e(z) were computed. The resulting e(z) with excellent matching with experimental measurements were then applied to the CLSM, Monte Carlo simulation was repeated until the modeled MTF, DQE(f) also match experimental measurement. Results: For a 150 micron FOS HL type CsI, e(z) varies between 0.56 to 0.45, and the MTF at 14 cycles/mm varies between 62.1% to 3.9%, from the front to the back of the scintillator. The overall MTF and DQE(f) at all frequencies are in excellent agreement with experimental measurements at all frequencies. Conclusion: We have developed a CLSM for columnar CsI scintillators with depth dependent gain and MTF, which were estimated from Monte Carlo simulation with novel optical simulation settings. Preliminary results showed excellent agreement between simulation results and experimental measurements. Future work is aimed at extending this approach to optimize CsI screen optic design and sensor structure for achieving higher DQE(f) in cone-beam CT, which uses high kVp.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

A two-level GPU-accelerated incomplete LU preconditioner for general sparse linear systems

This paper presents a parallel preconditioning approach based on incomplete LU (ILU) factorizations in the framework of Domain Decomposition (DD) for general sparse linear systems. We focus on distributed memory parallel architectures, specifically, those that are equipped with graphic processing units (GPUs). In addition to block-Jacobi, we present general purpose two-level ILU Schur complement-based approaches, where different strategies are presented to solve the coarse-level reduced system. These strategies are combined with modified ILU methods in the construction of the coarse-level operator, in order to effectively remove smooth errors by targeting an algebraically smooth vector. We leverage available GPU-based sparse matrix kernels to accelerate the setup and the solve phases of the proposed ILU preconditioner. We evaluate the efficiency of the proposed methods as a smoother for algebraic multigrid (AMG) and as a preconditioner for Krylov subspace methods on challenging anisotropic diffusion problems and a collection of general sparse matrices.

97 MATHEMATICS AND COMPUTING↗

Optimal Distributed Control of Spatially Invariant Time Varying Linear Systems

In this paper, the optimal distributed linear time varying H2 control problem for cone causal spatially invariant linear time varying (SILTV) systems is considered. This class of systems was initially defined in the work of Voulgaris et al. for cone causal spatially invariant (SI) linear time invariant (LTI) systems. First, the optimal time varying H2 problem is posed using a version of the Youla parameterization. This allows to transform the problem into an affine form which results in a convex but infinite dimensional distributed optimization. Next, the problem is solved by computing an operator projection on a class of time varying Youla parameters with a cone causal distributed structure. The cone causal spatially invariant systems are viewed as input-output multiplicative operators with a mixed causal time varying structure with respect to time, and spatially invariant with respect to the space dimension.

Djouadi, Seddik M.↗

Alternating Anderson–Richardson method: An efficient alternative to preconditioned Krylov methods for large, sparse linear systems

Here, we present the Alternating Anderson–Richardson (AAR) method: an efficient and scalable alternative to preconditioned Krylov solvers for the solution of large, sparse linear systems on high performance computing platforms. Specifically, we generalize the recently proposed Alternating Anderson–Jacobi (AAJ) method (Pratapa et al., 2016) to include preconditioning, discuss efficient parallel implementation, and provide serial MATLAB and parallel C/C++ implementations. In serial applications to nonsymmetric systems, we find that AAR is comparably robust to GMRES, using the same preconditioning, while often outperforming it in time to solution; and find AAR to be more robust than Bi-CGSTAB for the problems considered. In parallel applications to the Helmholtz and Poisson equations, we find that AAR shows superior strong and weak scaling to GMRES, Bi-CGSTAB, and Conjugate Gradient (CG) methods, using the same preconditioning, with consistently shorter times to solution at larger processor counts. Finally, in massively parallel applications to the Poisson equation, on up to 110,592 processors, we find that AAR shows superior strong and weak scaling to CG, with shorter minimum time to solution. We thus find that AAR offers a robust and efficient alternative to current state-of-the-art solvers, with increasing advantages as the number of processors grows.

97 MATHEMATICS AND COMPUTING↗

PCG method with Strang’s circulant preconditioner for Hermitian positive definite linear system in Riesz space fractional advection–dispersion equations

In this paper, preconditioned conjugate gradient (PCG) method with Strang’s circulant preconditioner is investigated to solve the Hermitian positive definite linear systems, which is result from the Crank–Nicolson (C-N) finite difference scheme with the weighted and shifted Grünwald difference (WSGD) operators to discretize the Riesz space fractional advection–dispersion equation (RSFADE). We show that the spectrum of the preconditioned matrix is clustered around 1, and the singular values of the preconditioned matrix are uniformly bounded away from zero under a certain condition, respectively; hence the PCG method, when applied to solving the preconditioned system, converges superlinearly. Moreover, the complexity in each iteration of the PCG method is O(Nlog N) via using the fast Fourier transforms, where N is the matrix size. Numerical experiments are included to demonstrate the effectiveness of our approach.

97 MATHEMATICS AND COMPUTING↗

Response analysis of a class of quasi-linear systems with fractional derivative excited by Poisson white noise

The Poisson white noise, as a typical non-Gaussian excitation, has attracted much attention recently. However, little work was referred to the study of stochastic systems with fractional derivative under Poisson white noise excitation. This paper investigates the stationary response of a class of quasi-linear systems with fractional derivative excited by Poisson white noise. The equivalent stochastic system of the original stochastic system is obtained. Then, approximate stationary solutions are obtained with the help of the perturbation method. Finally, two typical examples are discussed in detail to demonstrate the effectiveness of the proposed method. The analysis also shows that the fractional order and the fractional coefficient significantly affect the responses of the stochastic systems with fractional derivative.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Performance Models for the Spike Banded Linear System Solver

With availability of large-scale parallel platforms comprised of tens-of-thousands of processors and beyond, there is significant impetus for the development of scalable parallel sparse linear system solvers and preconditioners. An integral part of this design process is the development of performance models capable of predicting performance and providing accurate cost models for the solvers and preconditioners. There has been some work in the past on characterizing performance of the iterative solvers themselves. In this paper, we investigate the problem of characterizing performance and scalability of banded preconditioners. Recent work has demonstrated the superior convergence properties and robustness of banded preconditioners, compared to state-of-the-art ILU family of preconditioners as well as algebraic multigrid preconditioners. Furthermore, when used in conjunction with efficient banded solvers, banded preconditioners are capable of significantly faster time-to-solution. Our banded solver, the Truncated Spike algorithm is specifically designed for parallel performance and tolerance to deep memory hierarchies. Its regular structure is also highly amenable to accurate performance characterization. Using these characteristics, we derive the following results in this paper: (i) we develop parallel formulations of the Truncated Spike solver, (ii) we develop a highly accurate pseudo-analytical parallel performance model for our solver, (iii) we show excellent predication capabilities of our model – based on which we argue the high scalability of our solver. Our pseudo-analytical performance model is based on analytical performance characterization of each phase of our solver. These analytical models are then parameterized using actual runtime information on target platforms. An important consequence of our performance models is that they reveal underlying performance bottlenecks in both serial and parallel formulations. All of our results are validated on diverse heterogeneous multiclusters – platforms for which performance prediction is particularly challenging. Finally, we provide predict the scalability of the Spike algorithm using up to 65,536 cores with our model. In this paper we extend the results presented in the Ninth International Symposium on Parallel and Distributed Computing.

Manguoglu, Murat↗

The Cauchy Problem for Boltzmann Bi-linear Systems: The Mixing of Monatomic and Polyatomic Gases

Abstract From a unified vision of vector valued solutions in weighted Banach spaces, this paper establishes the existence and uniqueness for space homogeneous Boltzmann bi-linear systems with conservative collisional forms arising in complex gas dynamical structures. This broader vision is directly applied to dilute multi-component gas mixtures composed of both monatomic and polyatomic gases. Such models can be viewed as extensions of scalar Boltzmann binary elastic flows, as much as monatomic gas mixtures with disparate masses and single polyatomic gases, providing a unified approach for vector valued solutions in weighted Banach spaces. Novel aspects of this work include developing the extension of a general ODE theory in vector valued weighted Banach spaces, precise lower bounds for the collision frequency in terms of the weighted Banach norm, energy identities, angular or compact manifold averaging lemmas which provide coerciveness resulting into global in time stability, a new combinatorics estimate for p -binomial forms producing sharper estimates for the k -moments of bi-linear collisional forms. These techniques enable the Cauchy problem improvement that resolves the model with initial data corresponding to strictly positive and bounded initial vector valued mass and total energy, in addition to only a $$2^+$$ 2 + moment determined by the hard potential rates discrepancy, a result comparable in generality to the classical Cauchy theory of the scalar homogeneous Boltzmann equation.

Physics↗

A Multiple-Set Overlapping-Domain Decomposed Monte Carlo Synthetic Acceleration Method for Linear Systems

We present a multiple-set overlapping-domain decomposed strategy for parallelizing the Monte Carlo Synthetic Acceleration method. Monte Carlo Synthetic Acceleration methods use the Neumann-Ulam class of Monte Carlo solvers for linear systems to accelerate a fixed-point iteration sequence. Effective parallel algorithms for these methods require the parallelization of the underlying Neumann-Ulam solvers. To do this in a domain decomposed environment, we borrow strategies traditionally implemented in Monte Carlo particle transport to parallelize the problem. The parallel Neumann-Ulam and multiple-set overlapping-domain decomposition algorithms are presented along with parallel scaling data for the resulting implementation using the Titan Cray XK7 machine at Oak Ridge National Laboratory.

Computer Science↗

A cooperative conjugate gradient method for linear systems permitting efficient multi-thread implementation

This paper revisits, in a multi-thread context, the so-called multi-parameter or block conjugate gradient (B-CG) methods, first proposed as sequential algorithms by O’Leary and Brezinski, for the solution of the linear system Ax=b, for an n-dimensional symmetric positive definite matrix A. Instead of the scalar parameters of the classical CG algorithm, which minimizes a scalar functional at each iteration, multiple descent and conjugate directions are updated simultaneously. Implementation involves the use of multiple threads and the algorithm is referred to as cooperative CG (CCG) to emphasize that each thread now uses information that comes from the other threads. It is shown that for a sufficiently large matrix dimension n, the use of an optimal number of threads results in a worst case flop count of O(n{sup 7/3}) in exact arithmetic. Numerical experiments on a multi-core, multi-thread computer, for synthetic and real matrices, illustrate the theoretical results.

97 MATHEMATICS AND COMPUTING↗

GMRES with embedded ensemble propagation for the efficient solution of parametric linear systems in uncertainty quantification of computational models

In a previous work, embedded ensemble propagation was proposed to improve the efficiency of sampling-based uncertainty quantification methods of computational models on emerging computational architectures. It consists of simultaneously evaluating the model for a subset of samples together, instead of evaluating them individually. A first approach introduced to solve parametric linear systems with ensemble propagation is ensemble reduction. In Krylov methods for example, this reduction consists in coupling the samples together using an inner product that sums the sample contributions. Ensemble reduction has the advantages of being able to use optimized implementations of BLAS functions and having a stopping criterion which involves only one scalar. However, the reduction potentially decreases the rate of convergence due to the gathering of the spectra of the samples. In this paper, we investigate a second approach: ensemble propagation without ensemble reduction in the case of GMRES. This second approach solves each sample simultaneously but independently to improve the convergence compared to ensemble reduction. This raises two new issues which are solved in this paper: the fact that optimized implementations of BLAS functions cannot be used anymore and that ensemble divergence, whereby individual samples within an ensemble must follow different code execution paths, can occur. We tackle those issues by implementing a high-performing ensemble GEMV and by using masks. The proposed ensemble GEMV leads to a similar cost per GMRES iteration for both approaches, i.e. with and without reduction. For illustration, we study the performances of the new linear solver in the context of a mesh tying problem. Furthermore, this example demonstrates improved ensemble propagation speed-up without reduction.

BLAS↗