Due to the rapid advance of the integrated circuit technology, power grid analysis usually imposes a severe computational challenge, where linear equations with millions or even billions of unknowns need to be solved....
详细信息
ISBN:
(纸本)9781665445078
Due to the rapid advance of the integrated circuit technology, power grid analysis usually imposes a severe computational challenge, where linear equations with millions or even billions of unknowns need to be solved. Recent graph spectral sparsification techniques have shown promising performance in accelerating power grid analysis. However, previous graph sparsification based iterative solvers are restricted by difficulty of parallelization. Existing graph sparsification algorithms are implemented under the assumption of serial computing, while factorization and backward/forward substitution of the sparsifier's Laplacian matrix are also hard to parallelize. On the other hand, partition based iterative methods which can be easily parallelized lack a direct control of the relative condition number of the preconditioner and consume more memory. In this work, we propose a novel parallel iterative solver for scalable power grid analysis by integrating graph sparsification techniques and partition based methods. We first propose a practically-efficient parallel graph sparsification algorithm. Then, domain decomposition method is leveraged to solve the sparsifier's Laplacian matrix. An efficient graph sparsification based parallel preconditioner is obtained, which not only leads to fast convergence but also enjoys ease of parallelization. Extensive experiments are carried out to demonstrate the superior efficiency of the proposed solver for large-scale power grid analysis, showing 5.2X speedup averagely over the state-of-the-art parallel iterative solver. Moreover, it solves a real-world power grid matrix with 0.36 billion nodes and 8.7 billion nonzeros within 23 minutes on a 16-core machine, which is 9.5X faster than the best result of sequential graph sparsification based solver.
A preconditionedconjugategradient (PCG)-based domain decomposition method was given in [11] and [12] for the solution of linear equations arising in the finite element method applied to the elliptic Neumann problem....
详细信息
In this paper we propose a superfast implementation of Wilson's method for the spectral factorization of Laurent polynomials based on a preconditioned conjugate gradient algorithm. The new computational scheme fol...
详细信息
ISBN:
(纸本)0819445584
In this paper we propose a superfast implementation of Wilson's method for the spectral factorization of Laurent polynomials based on a preconditioned conjugate gradient algorithm. The new computational scheme follows by exploiting several recently established connections between the considered factorization problem and the solution of certain discrete-time Lyapunov matrix equations whose coefficients are in controllable canonical form. The results of many numerical experiments even involving polynomials of very high degree are reported and discussed by showing that our preconditioning strategy is quite effective just when starting the iterative phase with a roughly approximation of the sought factor. Thus, our approach provides an efficient refinement procedure which is particularly suited to be combined with linearly convergent factorization algorithms when suffering from a very slow convergence due to the occurrence of roots close to the unit circle.
This paper presents a three-dimensional density inversion software called DenInv3D that operates on gravity and gravity gradient data. The software performs inversion modelling, kernel function calculation, and invers...
详细信息
This paper presents a three-dimensional density inversion software called DenInv3D that operates on gravity and gravity gradient data. The software performs inversion modelling, kernel function calculation, and inversion calculations using the improved preconditionedconjugategradient (PCG) algorithm. In the PCG algorithm, due to the uncertainty of empirical parameters, such as the Lagrange multiplier, we use the inflection point of the L-curve as the regularisation parameter. The software can construct unequally spaced grids and perform inversions using such grids, which enables changing the resolution of the inversion results at different depths. Through inversion of airborne gradiometry data on the Australian Kauring test site, we discovered that anomalous blocks of different sizes are present within the study area in addition to the central anomalies. The software of DenInv3D can be downloaded from http://159.226.162.30.
暂无评论