Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “conjugate gradient”

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 19 records

A projected preconditioned conjugate gradient algorithm for computing many extreme eigenpairs of a Hermitian matrix

We present an iterative algorithm for computing an invariant subspace associated with the algebraically smallest eigenvalues of a large sparse or structured Hermitian matrix A. We are interested in the case in which the dimension of the invariant subspace is large (e.g., over several hundreds or thousands) even though it may still be small relative to the dimension of A. These problems arise from, for example, density functional theory (DFT) based electronic structure calculations for complex materials. The key feature of our algorithm is that it performs fewer Rayleigh–Ritz calculations compared to existing algorithms such as the locally optimal block preconditioned conjugate gradient or the Davidson algorithm. It is a block algorithm, and hence can take advantage of efficient BLAS3 operations and be implemented with multiple levels of concurrency. We discuss a number of practical issues that must be addressed in order to implement the algorithm efficiently on a high performance computer.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Accelerated Sparse Recovery via Gradient Descent with Nonlinear Conjugate Gradient Momentum

This paper applies an idea of adaptive momentum for the nonlinear conjugate gradient to accelerate optimization problems in sparse recovery. Specifically, we consider two types of minimization problems: a (single) differentiable function and the sum of a non-smooth function and a differentiable function. In the first case, we adopt a fixed step size to avoid the traditional line search and establish the convergence analysis of the proposed algorithm for a quadratic problem. This acceleration is further incorporated with an operator splitting technique to deal with the non-smooth function in the second case. As a result, we use the convex ι 1 and the nonconvex ι 1 – ι 2 functionals as two case studies to demonstrate the efficiency of the proposed approaches over traditional methods.

97 MATHEMATICS AND COMPUTING↗

M-step preconditioned conjugate gradient methods

Preconditioned conjugate gradient methods for solving sparse symmetric and positive finite systems of linear equations are described. Necessary and sufficient conditions are given for when these preconditioners can be used and an analysis of their effectiveness is given. Efficient computer implementations of these methods are discussed and results on the CYBER 203 and the Finite Element Machine under construction at NASA Langley Research Center are included.

Adams, L.↗

Parallel conjugate gradient algorithms for manipulator dynamic simulation

Parallel conjugate gradient algorithms for the computation of multibody dynamics are developed for the specialized case of a robot manipulator. For an n-dimensional positive-definite linear system, the Classical Conjugate Gradient (CCG) algorithms are guaranteed to converge in n iterations, each with a computation cost of O(n); this leads to a total computational cost of O(n sq) on a serial processor. A conjugate gradient algorithms is presented that provide greater efficiency using a preconditioner, which reduces the number of iterations required, and by exploiting parallelism, which reduces the cost of each iteration. Two Preconditioned Conjugate Gradient (PCG) algorithms are proposed which respectively use a diagonal and a tridiagonal matrix, composed of the diagonal and tridiagonal elements of the mass matrix, as preconditioners. Parallel algorithms are developed to compute the preconditioners and their inversions in O(log sub 2 n) steps using n processors. A parallel algorithm is also presented which, on the same architecture, achieves the computational time of O(log sub 2 n) for each iteration. Simulation results for a seven degree-of-freedom manipulator are presented. Variants of the proposed algorithms are also developed which can be efficiently implemented on the Robot Mathematics Processor (RMP).

Fijany, Amir↗

The multigrid preconditioned conjugate gradient method

A multigrid preconditioned conjugate gradient method (MGCG method), which uses the multigrid method as a preconditioner of the PCG method, is proposed. The multigrid method has inherent high parallelism and improves convergence of long wavelength components, which is important in iterative methods. By using this method as a preconditioner of the PCG method, an efficient method with high parallelism and fast convergence is obtained. First, it is considered a necessary condition of the multigrid preconditioner in order to satisfy requirements of a preconditioner of the PCG method. Next numerical experiments show a behavior of the MGCG method and that the MGCG method is superior to both the ICCG method and the multigrid method in point of fast convergence and high parallelism. This fast convergence is understood in terms of the eigenvalue analysis of the preconditioned matrix. From this observation of the multigrid preconditioner, it is realized that the MGCG method converges in very few iterations and the multigrid preconditioner is a desirable preconditioner of the conjugate gradient method.

Tatebe, Osamu↗

Minimizing inner product data dependencies in conjugate gradient iteration

The amount of concurrency available in conjugate gradient iteration is limited by the summations required in the inner product computations. The inner product of two vectors of length N requires time c log(N), if N or more processors are available. This paper describes an algebraic restructuring of the conjugate gradient algorithm which minimizes data dependencies due to inner product calculations. After an initial start up, the new algorithm can perform a conjugate gradient iteration in time c*log(log(N)).

Vanrosendale, J.↗

Efficient conjugate gradient algorithms for computation of the manipulator forward dynamics

The applicability of conjugate gradient algorithms for computation of the manipulator forward dynamics is investigated. The redundancies in the previously proposed conjugate gradient algorithm are analyzed. A new version is developed which, by avoiding these redundancies, achieves a significantly greater efficiency. A preconditioned conjugate gradient algorithm is also presented. A diagonal matrix whose elements are the diagonal elements of the inertia matrix is proposed as the preconditioner. In order to increase the computational efficiency, an algorithm is developed which exploits the synergism between the computation of the diagonal elements of the inertia matrix and that required by the conjugate gradient algorithm.

Fijany, Amir↗

Approximate error conjugation gradient minimization methods

In one embodiment, a method includes selecting a subset of rays from a set of all rays to use in an error calculation for a constrained conjugate gradient minimization problem, calculating an approximate error using the subset of rays, and calculating a minimum in a conjugate gradient direction based on the approximate error. In another embodiment, a system includes a processor for executing logic, logic for selecting a subset of rays from a set of all rays to use in an error calculation for a constrained conjugate gradient minimization problem, logic for calculating an approximate error using the subset of rays, and logic for calculating a minimum in a conjugate gradient direction based on the approximate error. In other embodiments, computer program products, methods, and systems are described capable of using approximate error in constrained conjugate gradient minimization problems.

97 MATHEMATICS AND COMPUTING↗

Solving linear equations with messenger-field and conjugate gradient techniques: An application to CMB data analysis

We discuss linear system solvers invoking a messenger-field and compare them with (preconditioned) conjugate gradient approaches. We show that the messenger-field techniques correspond to fixed point iterations of an appropriately preconditioned initial system of linear equations. We then argue that a conjugate gradient solver applied to the same preconditioned system, or equivalently a preconditioned conjugate gradient solver using the same preconditioner and applied to the original system, will in general ensure at least a comparable and typically better performance in terms of the number of iterations to convergence and time-to-solution. We illustrate our conclusions with two common examples drawn from the cosmic microwave background (CMB) data analysis: Wiener filtering and map-making. In addition, and contrary to the standard lore in the CMB field, we show that the performance of the preconditioned conjugate gradient solver can depend significantly on the starting vector. In conclusion, this observation seems of particular importance in the cases of map-making of high signal-to-noise ratio sky maps and therefore should be of relevance for the next generation of CMB experiments.

79 ASTRONOMY AND ASTROPHYSICS↗

Ground state wave functions for single-band Hubbard models from the Gutzwiller conjugate gradient minimisation theory

The Gutzwiller conjugate gradient minimisation (GCGM) theory is an ab initio quantum many-body theory for computing the ground-state properties of infinite systems. Previous applications of GCGM provides satisfying accuracy of ground-state energy of Hubbard models. In the current work, we address the problem of whether the obtained wave function is a good approximation for the true ground state by comparing the correlation functions with the benchmark data. Additionally, our results confirms the accuracy of the reproduced ground state of the regular Hubbard model, but with some exception for the frustrated Hubbard model.

74 ATOMIC AND MOLECULAR PHYSICS↗

Ground-state properties of the Hubbard model in one and two dimensions from the Gutzwiller conjugate gradient minimization theory

We introduce Gutzwiller conjugate gradient minimization (GCGM) theory, an ab initio quantum many-body theory for computing the ground-state properties of infinite systems. GCGM uses the Gutzwiller wave function but does not use the commonly adopted Gutzwiller approximation (GA), which is a major source of inaccuracy. Instead, the theory uses an approximation that is based on the occupation probability of the on-site configurations, rather than approximations that decouple the site-site correlations as used in the GA. We test the theory in the one-dimensional and two-dimensional Hubbard models at various electron densities and find that GCGM reproduces energies and double occupancies in reasonable agreement with benchmark data at a very small computational cost.

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗

A posteriori superlinear convergence bounds for block conjugate gradient

In this paper, we extend to the block case the a posteriori bound showing superlinear convergence of the conjugate gradient method developed by van der Vorst and Vuik in [J. Comput. Applied Math., 48 (1993), pp. 327–341]. That is, we obtain similar bounds but now for the block conjugate gradient method. We also present a series of computational experiments, illustrating the validity of the bound developed here as well as the bound by Simoncini and Szyld from [SIAM Review, 47 (2005), pp. 247–272] using angles between subspaces. Using these bounds, we make some observations on the onset of superlinearity and how this onset depends on the eigenvalue distribution and the block size.

97 MATHEMATICS AND COMPUTING↗

Conjugate gradient type methods for linear systems with complex symmetric coefficient matrices

We consider conjugate gradient type methods for the solution of large sparse linear system Ax equals b with complex symmetric coefficient matrices A equals A(T). Such linear systems arise in important applications, such as the numerical solution of the complex Helmholtz equation. Furthermore, most complex non-Hermitian linear systems which occur in practice are actually complex symmetric. We investigate conjugate gradient type iterations which are based on a variant of the nonsymmetric Lanczos algorithm for complex symmetric matrices. We propose a new approach with iterates defined by a quasi-minimal residual property. The resulting algorithm presents several advantages over the standard biconjugate gradient method. We also include some remarks on the obvious approach to general complex linear systems by solving equivalent real linear systems for the real and imaginary parts of x. Finally, numerical experiments for linear systems arising from the complex Helmholtz equation are reported.

Freund, Roland↗

On conjugate gradient type methods and polynomial preconditioners for a class of complex non-Hermitian matrices

Conjugate gradient type methods are considered for the solution of large linear systems Ax = b with complex coefficient matrices of the type A = T + i(sigma)I where T is Hermitian and sigma, a real scalar. Three different conjugate gradient type approaches with iterates defined by a minimal residual property, a Galerkin type condition, and an Euclidian error minimization, respectively, are investigated. In particular, numerically stable implementations based on the ideas behind Paige and Saunder's SYMMLQ and MINRES for real symmetric matrices are proposed. Error bounds for all three methods are derived. It is shown how the special shift structure of A can be preserved by using polynomial preconditioning. Results on the optimal choice of the polynomial preconditioner are given. Also, some numerical experiments for matrices arising from finite difference approximations to the complex Helmholtz equation are reported.

Freund, Roland↗