Journal articles: 'Multilevel Krylov Subspace Splitting'

1

Bai, Zhong-Zhi. "Regularized HSS iteration methods for stabilized saddle-point problems." IMA Journal of Numerical Analysis 39, no. 4 (July 31, 2018): 1888–923. http://dx.doi.org/10.1093/imanum/dry046.

Full text

Abstract:

Abstract We extend the regularized Hermitian and skew-Hermitian splitting (RHSS) iteration methods for standard saddle-point problems to stabilized saddle-point problems and establish the corresponding unconditional convergence theory for the resulting methods. Besides being used as stationary iterative solvers, this class of RHSS methods can also be used as preconditioners for Krylov subspace methods. It is shown that the eigenvalues of the corresponding preconditioned matrix are clustered at a small number of points in the interval $(0, \, 2)$ when the iteration parameter is close to $0$ and, furthermore, they can be clustered near $0$ and $2$ when the regularization matrix is appropriately chosen. Numerical results on stabilized saddle-point problems arising from finite element discretizations of an optimal boundary control problem and of a Cahn–Hilliard image inpainting problem, as well as from the Gauss–Newton linearization of a nonlinear image restoration problem, show that the RHSS iteration method significantly outperforms the Hermitian and skew-Hermitian splitting iteration method in iteration counts and computing times when they are used either as linear iterative solvers or as matrix splitting preconditioners for Krylov subspace methods, and optimal convergence behavior can be achieved when using inexact variants of the proposed RHSS preconditioners.

APA, Harvard, Vancouver, ISO, and other styles

2

Tian, Zhaolu, Xiaojing Li, and Zhongyun Liu. "A general multi-step matrix splitting iteration method for computing PageRank." Filomat 35, no. 2 (2021): 679–706. http://dx.doi.org/10.2298/fil2102679t.

Full text

Abstract:

Based on the general inner-outer (GIO) iteration method [5,34] and the iteration framework [6], we present a general multi-step matrix splitting (GMMS) iteration method for computing PageRank, and analyze its overall convergence property. Moreover, the same idea can be used as a preconditioning technique for accelerating the Krylov subspace methods, such as GMRES method. Finally, several numerical examples are given to illustrate the effectiveness of the proposed algorithm.

APA, Harvard, Vancouver, ISO, and other styles

3

Huang, Yunying, and Guoliang Chen. "A relaxed block splitting preconditioner for complex symmetric indefinite linear systems." Open Mathematics 16, no. 1 (June 7, 2018): 561–73. http://dx.doi.org/10.1515/math-2018-0051.

Full text

Abstract:

AbstractIn this paper, we propose a relaxed block splitting preconditioner for a class of complex symmetric indefinite linear systems to accelerate the convergence rate of the Krylov subspace iteration method and the relaxed preconditioner is much closer to the original block two-by-two coefficient matrix. We study the spectral properties and the eigenvector distributions of the corresponding preconditioned matrix. In addition, the degree of the minimal polynomial of the preconditioned matrix is also derived. Finally, some numerical experiments are presented to illustrate the effectiveness of the relaxed splitting preconditioner.

APA, Harvard, Vancouver, ISO, and other styles

4

Xiong, Jin-Song. "Generalized accelerated AOR splitting iterative method for generalized saddle point problems." AIMS Mathematics 7, no. 5 (2022): 7625–41. http://dx.doi.org/10.3934/math.2022428.

Full text

Abstract:

<abstract><p>Generalized accelerated AOR (GAAOR) splitting iterative method for the generalized saddle point problems is proposed in this paper. The iterative scheme and the convergence of the GAAOR splitting method are researched. The eigenvalues distributions of its preconditioned matrix is discussed under {two different choices of the parameter matrix Q}. The resulting GAAOR preconditioner is used to precondition Krylov subspace method such as the restarted generalized minimal residual (GMRES) method for solving the equivalent formulation of the generalized saddle point problems. The theoretical results and effectiveness of the GAAOR splitting iterative method are supported by {some} numerical examples.</p></abstract>

APA, Harvard, Vancouver, ISO, and other styles

5

Luo, Jia-Min, Hou-Biao Li, and Wei-Bo Wei. "Block splitting preconditioner for time-space fractional diffusion equations." Electronic Research Archive 30, no. 3 (2022): 780–97. http://dx.doi.org/10.3934/era.2022041.

Full text

Abstract:

<abstract><p>For solving a block lower triangular Toeplitz linear system arising from the time-space fractional diffusion equations more effectively, a single-parameter two-step split iterative method (TSS) is introduced, its convergence theory is established and the corresponding preconditioner is also presented. Theoretical analysis shows that the original coefficient matrix after preconditioned can be expressed as the sum of the identity matrix, a low-rank matrix, and a small norm matrix. Numerical experiments show that the preconditioner improve the calculation efficiency of the Krylov subspace iteration method.</p></abstract>

APA, Harvard, Vancouver, ISO, and other styles

6

Lei, Siu-Long, Xu Chen, and Xinhe Zhang. "Multilevel Circulant Preconditioner for High-Dimensional Fractional Diffusion Equations." East Asian Journal on Applied Mathematics 6, no. 2 (May 2016): 109–30. http://dx.doi.org/10.4208/eajam.060815.180116a.

Full text

Abstract:

AbstractHigh-dimensional two-sided space fractional diffusion equations with variable diffusion coefficients are discussed. The problems can be solved by an implicit finite difference scheme that is proven to be uniquely solvable, unconditionally stable and first-order convergent in the infinity norm. A nonsingular multilevel circulant pre-conditoner is proposed to accelerate the convergence rate of the Krylov subspace linear system solver efficiently. The preconditoned matrix for fast convergence is a sum of the identity matrix, a matrix with small norm, and a matrix with low rank under certain conditions. Moreover, the preconditioner is practical, with an O(NlogN) operation cost and O(N) memory requirement. Illustrative numerical examples are also presented.

APA, Harvard, Vancouver, ISO, and other styles

7

Li, Cui-Xia, Yan-Jun Liang, and Shi-Liang Wu. "Generalized Preconditioned MHSS Method for a Class of Complex Symmetric Linear Systems." Abstract and Applied Analysis 2014 (2014): 1–9. http://dx.doi.org/10.1155/2014/206821.

Full text

Abstract:

Based on the modified Hermitian and skew-Hermitian splitting (MHSS) and preconditioned MHSS (PMHSS) methods, a generalized preconditioned MHSS (GPMHSS) method for a class of complex symmetric linear systems is presented. Theoretical analysis gives an upper bound for the spectral radius of the iteration matrix. From a practical point of view, we have analyzed and implemented inexact GPMHSS (IGPMHSS) iteration, which employs Krylov subspace methods as its inner processes. Numerical experiments are reported to confirm the efficiency of the proposed methods.

APA, Harvard, Vancouver, ISO, and other styles

8

Chen, Shanqin. "Krylov SSP Integrating Factor Runge–Kutta WENO Methods." Mathematics 9, no. 13 (June 24, 2021): 1483. http://dx.doi.org/10.3390/math9131483.

Full text

Abstract:

Weighted essentially non-oscillatory (WENO) methods are especially efficient for numerically solving nonlinear hyperbolic equations. In order to achieve strong stability and large time-steps, strong stability preserving (SSP) integrating factor (IF) methods were designed in the literature, but the methods there were only for one-dimensional (1D) problems that have a stiff linear component and a non-stiff nonlinear component. In this paper, we extend WENO methods with large time-stepping SSP integrating factor Runge–Kutta time discretization to solve general nonlinear two-dimensional (2D) problems by a splitting method. How to evaluate the matrix exponential operator efficiently is a tremendous challenge when we apply IF temporal discretization for PDEs on high spatial dimensions. In this work, the matrix exponential computation is approximated through the Krylov subspace projection method. Numerical examples are shown to demonstrate the accuracy and large time-step size of the present method.

APA, Harvard, Vancouver, ISO, and other styles

9

Luo, Wei-Hua, and Ting-Zhu Huang. "A Parameterized Splitting Preconditioner for Generalized Saddle Point Problems." Journal of Applied Mathematics 2013 (2013): 1–6. http://dx.doi.org/10.1155/2013/489295.

Full text

Abstract:

By using Sherman-Morrison-Woodbury formula, we introduce a preconditioner based on parameterized splitting idea for generalized saddle point problems which may be singular and nonsymmetric. By analyzing the eigenvalues of the preconditioned matrix, we find that whenαis big enough, it has an eigenvalue at 1 with multiplicity at leastn, and the remaining eigenvalues are all located in a unit circle centered at 1. Particularly, when the preconditioner is used in general saddle point problems, it guarantees eigenvalue at 1 with the same multiplicity, and the remaining eigenvalues will tend to 1 as the parameterα→0. Consequently, this can lead to a good convergence when some GMRES iterative methods are used in Krylov subspace. Numerical results of Stokes problems and Oseen problems are presented to illustrate the behavior of the preconditioner.

APA, Harvard, Vancouver, ISO, and other styles

10

Li, Yan-Ran, Xin-Hui Shao, and Shi-Yu Li. "New Preconditioned Iteration Method Solving the Special Linear System from the PDE-Constrained Optimal Control Problem." Mathematics 9, no. 5 (March 2, 2021): 510. http://dx.doi.org/10.3390/math9050510.

Full text

Abstract:

In many fields of science and engineering, partial differential equation (PDE) constrained optimal control problems are widely used. We mainly solve the optimization problem constrained by the time-periodic eddy current equation in this paper. We propose the three-block splitting (TBS) iterative method and proved that it is unconditionally convergent. At the same time, the corresponding TBS preconditioner is derived from the TBS iteration method, and we studied the spectral properties of the preconditioned matrix. Finally, numerical examples in two-dimensions is applied to demonstrate the advantages of the TBS iterative method and TBS preconditioner with the Krylov subspace method.

APA, Harvard, Vancouver, ISO, and other styles

11

Demyanko, Kirill V., Igor E. Kaporin, and Yuri M. Nechepurenko. "Inexact Newton method for the solution of eigenproblems arising in hydrodynamic temporal stability analysis." Journal of Numerical Mathematics 28, no. 1 (March 26, 2020): 1–14. http://dx.doi.org/10.1515/jnma-2019-0021.

Full text

Abstract:

AbstractThe inexact Newton method developed earlier for computing deflating subspaces associated with separated groups of finite eigenvalues of regular linear large sparse non-Hermitian matrix pencils is specialized to solve eigenproblems arising in the hydrodynamic temporal stability analysis. To this end, for linear systems to be solved at each step of the Newton method, a new efficient MLILU2 preconditioner based on the multilevel 2nd order incomplete LU-factorization is proposed. A special variant of Krylov subspace method IDR2 with right preconditioning is developed. In comparison with GMRES it requires much smaller workspace while may converge considerably faster than BiCGStab. The effectiveness of the proposed methods is illustrated with matrix pencils of order up to 3.1 ⋅ 106 arising in the temporal linear stability analysis of a typical hydrodinamic flow.

APA, Harvard, Vancouver, ISO, and other styles

12

Ran, Yu-Hong, Jun-Gang Wang, and Dong-Ling Wang. "On Preconditioners Based on HSS for the Space Fractional CNLS Equations." East Asian Journal on Applied Mathematics 7, no. 1 (January 31, 2017): 70–81. http://dx.doi.org/10.4208/eajam.190716.051116b.

Full text

Abstract:

AbstractThe space fractional coupled nonlinear Schrödinger (CNLS) equations are discretized by an implicit conservative difference scheme with the fractional centered difference formula, which is unconditionally stable. The coefficient matrix of the discretized linear system is equal to the sum of a complex scaled identity matrix which can be written as the imaginary unit times the identity matrix and a symmetric Toeplitz-plusdiagonal matrix. In this paper, we present new preconditioners based on Hermitian and skew-Hermitian splitting (HSS) for such Toeplitz-like matrix. Theoretically, we show that all the eigenvalues of the resulting preconditioned matrices lie in the interior of the disk of radius 1 centered at the point (1,0). Thus Krylov subspace methods with the proposed preconditioners converge very fast. Numerical examples are given to illustrate the effectiveness of the proposed preconditioners.

APA, Harvard, Vancouver, ISO, and other styles

13

Yuan, Yu-Xin, A.-Man Li, Ting Hu, and Hong Liu. "An anisotropic multilevel preconditioner for solving the Helmholtz equation with unequal directional sampling intervals." GEOPHYSICS 85, no. 6 (October 13, 2020): T293—T300. http://dx.doi.org/10.1190/geo2019-0330.1.

Full text

Abstract:

An efficient finite-difference method for solving the isotropic Helmholtz equation relies on a discretization scheme and an appropriate solver. Accordingly, we have adopted an average-derivative optimal scheme that has two advantages: (1) it can be applied to unequal directional sampling intervals and (2) it requires less than four grid points of sampling per wavelength. Direct methods are not of interest for industry-sized problems due to the high memory requirements; Krylov subspace methods such as the biconjugate gradient stabilized method and the flexible generalized minimal residual method that combine a multigrid-based preconditioner are better alternatives. However, standard geometric multigrid algorithms fail to converge when there exist unequal directional sampling intervals; this is called anisotropic grids in terms of the multigrid. We first review our previous research on 2D anisotropic grids: the semicoarsening strategy, line-wise relaxation operator, and matrix-dependent interpolation were used to modify the standard V-cycle multigrid algorithms, resulting in convergence. Although directly extending to the 3D case by substituting line relaxation for plane relaxation deteriorates the convergence rate considerably, we then find that a multilevel generalized minimal residual preconditioner-combined semicoarsening strategy is more suitable for anisotropic grids and the convergence rate is faster in the 2D and 3D cases. The results of the numerical experiments indicate that the standard geometric multigrid does not work for anisotropic grids, whereas our method demonstrates a faster convergence rate than the previous method.

APA, Harvard, Vancouver, ISO, and other styles

14

Axelsson, Owe, Maya Neytcheva, and Zhao-Zheng Liang. "PARALLEL SOLUTION METHODS AND PRECONDITIONERS FOR EVOLUTION EQUATIONS." Mathematical Modelling and Analysis 23, no. 2 (April 18, 2018): 287–308. http://dx.doi.org/10.3846/mma.2018.018.

Full text

Abstract:

The recent development of the high performance computer platforms shows a clear trend towards heterogeneity and hierarchy. In order to utilize the computational power, particular attention must be paid to ﬁnding new algorithms or adjust existing ones so that they better match the HPC computer architecture. In this work we consider an alternative to classical time-stepping methods based on use of time-harmonic properties and discuss solution approaches that allow eﬃcient utilization of modern HPC resources. The method in focus is based on a truncated Fourier expansion of the solution of an evolutionary problem. The analysis is done for linear equations and it is remarked on the possibility to use two- or multilevel mesh methods for nonlinear problems, which can enable further, even higher degree of parallelization. The arising block matrix system to be solved admits a two-by-two block form with square blocks, for which a very eﬃcient preconditioner exists. It leads to tight eigenvalue bounds for the preconditioned matrix and, hence, to a very fast convergence of a preconditioned Krylov subspace or iterative reﬁnement method. The analytical background is shown as well as some illustrating numerical examples.

APA, Harvard, Vancouver, ISO, and other styles

15

Mo, Tieqiang, and Renfa Li. "Iteratively solving sparse linear system based on PaRSEC task scheduling." International Journal of High Performance Computing Applications 34, no. 3 (January 13, 2020): 306–15. http://dx.doi.org/10.1177/1094342019899997.

Full text

Abstract:

With the new architecture and new programming paradigms such as task-based scheduling emerging in the parallel high performance computing area, it is of great importance to utilize these features to tune the monolithic computing codes. In this article, the classical conjugate gradient algorithms targeting at sparse linear system Ax = b in Krylov subspace are pipelining to execute interdependent tasks on Parallel Runtime Scheduling and Execution Controller (PaRSEC) runtime. Firstly, the sparse matrix A is split in rows to unfold more coarse-grained parallelism. Secondly, the partitioned sub-vectors are not assembled into one full vector in RAM to run sparse matrix–vector product (SpMV) operations for eliminating the communication overhead. Moreover, in the SpMV computation, if all elements of one column in the split sub-matrix are zeros, the corresponding product operations of these elements may be removed by reorganizing sub-vectors. Finally, the latency of migrating sub-vector is partially overlapped by the duration of performing SpMV operations through the further splitting in columns of sparse matrix on GPUs. In experiments, a series of tests demonstrate that optimal speedup and higher pipelining efficiency has been achieved for the pipelined task scheduling on PaRSEC runtime. Fusing SpMV concurrency and dot product pipelining can achieve higher speedup and efficiency.

APA, Harvard, Vancouver, ISO, and other styles

16

Alpert, C. J., A. E. Caldwell, T. F. Chan, D. J. H. Huang, A. B. Kahng, I. L. Markov, and M. S. Moroz. "Analytical Engines are Unnecessary in Top-down Partitioning-based Placement." VLSI Design 10, no. 1 (January 1, 1999): 99–116. http://dx.doi.org/10.1155/1999/93607.

Full text

Abstract:

The top-down “quadratic placement” methodology is rooted in such works as [36, 9, 32] and is reputedly the basis of commercial and in-house VLSI placement tools. This methodology iterates between two basic steps: solving sparse systems of linear equations to achieve a continuous placement solution, and “legalization” of the placement by transportation or partitioning. Our work, which extends [5], studies implementation choices and underlying motivations for the quadratic placement methodology. We first recall some observations from [5], e.g., that (i) Krylov subspace engines for solving sparse linear systems are more effective than traditional successive over-relaxation (SOR) engines [33] and (ii) that correlation convergence criteria can maintain solution quality while using substantially fewer solver iterations. The focus of our investigation is the coupling of numerical solvers to iterative partitioners that is a hallmark of the quadratic placement methodology. We provide evidence that this coupling may have historically been motivated by the pre-1990’s weakness of min-cut partitioners, i.e., numerical engines were needed to provide helpful hints to weak min-cut partitioners. In particular, we show that a modern multilevel FM implementation [2] derives no benefit from such coupling. We also show that most insights obtained from study of individual min-cut partitioning instances (within the top-down placement) also hold within the overall context of a complete top-down placer implementation.

APA, Harvard, Vancouver, ISO, and other styles

17

Kong, Fande, Yaqi Wang, Derek R. Gaston, Cody J. Permann, Andrew E. Slaughter, Alexander D. Lindsay, Mark D. DeHart, and Richard C. Martineau. "A Highly Parallel Multilevel Newton--Krylov--Schwarz Method with Subspace-Based Coarsening and Partition-Based Balancing for the Multigroup Neutron Transport Equation on Three-Dimensional Unstructured Meshes." SIAM Journal on Scientific Computing 42, no. 5 (January 2020): C193—C220. http://dx.doi.org/10.1137/19m1249060.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Hajibeygi, H., S. H. H. Lee, and I. Lunati. "Accurate and Efficient Simulation of Multiphase Flow in a Heterogeneous Reservoir With Error Estimate and Control in the Multiscale Finite-Volume Framework." SPE Journal 17, no. 04 (October 17, 2012): 1071–83. http://dx.doi.org/10.2118/141954-pa.

Full text

Abstract:

Summary The multiscale finite-volume (MSFV) method is designed to reduce the computational cost of elliptic and parabolic problems with highly heterogeneous anisotropic coefficients. The reduction is achieved by splitting the original global problem into a set of local problems (with approximate local boundary conditions) coupled by a coarse global problem. It has been shown recently that the numerical errors in MSFV results can be reduced systematically with an iterative procedure that provides a conservative velocity field after any iteration step. The iterative MSFV (i-MSFV) method can be derived with an improved (smoothed) multiscale solution to enhance the localization conditions, with a Krylov subspace method [e.g., the generalized-minimal-residual (GMRES) algorithm] preconditioned by the MSFV system, or with a combination of both. In a multiphase-flow system, a balance between accuracy and computational efficiency should be achieved by finding a minimum number of i-MSFV iterations (on pressure), which is necessary to achieve the desired accuracy in the saturation solution. In this work, we extend the i-MSFV method to sequential implicit simulation of time-dependent problems. To control the error of the coupled saturation/pressure system, we analyze the transport error caused by an approximate velocity field. We then propose an error-control strategy on the basis of the residual of the pressure equation. At the beginning of simulation, the pressure solution is iterated until a specified accuracy is achieved. To minimize the number of iterations in a multiphase-flow problem, the solution at the previous timestep is used to improve the localization assumption at the current timestep. Additional iterations are used only when the residual becomes larger than a specified threshold value. Numerical results show that only a few iterations on average are necessary to improve the MSFV results significantly, even for very challenging problems. Therefore, the proposed adaptive strategy yields efficient and accurate simulation of multiphase flow in heterogeneous porous media.

APA, Harvard, Vancouver, ISO, and other styles

19

Trivedi, Rahul, Logan Su, Jesse Lu, Martin F. Schubert, and Jelena Vuckovic. "Data-driven acceleration of photonic simulations." Scientific Reports 9, no. 1 (December 2019). http://dx.doi.org/10.1038/s41598-019-56212-5.

Full text

Abstract:

AbstractDesigning modern photonic devices often involves traversing a large parameter space via an optimization procedure, gradient based or otherwise, and typically results in the designer performing electromagnetic simulations of a large number of correlated devices. In this paper, we investigate the possibility of accelerating electromagnetic simulations using the data collected from such correlated simulations. In particular, we present an approach to accelerate the Generalized Minimal Residual (GMRES) algorithm for the solution of frequency-domain Maxwell’s equations using two machine learning models (principal component analysis and a convolutional neural network). These data-driven models are trained to predict a subspace within which the solution of the frequency-domain Maxwell’s equations approximately lies. This subspace is then used for augmenting the Krylov subspace generated during the GMRES iterations, thus effectively reducing the size of the Krylov subspace and hence the number of iterations needed for solving Maxwell’s equations. By training the proposed models on a dataset of wavelength-splitting gratings, we show an order of magnitude reduction (~10–50) in the number of GMRES iterations required for solving frequency-domain Maxwell’s equations.

APA, Harvard, Vancouver, ISO, and other styles

20

Dufrechou, Ernesto. "Accelerating advanced preconditioning methods on hybrid architectures." CLEI Electronic Journal 24, no. 1 (April 14, 2021). http://dx.doi.org/10.19153/cleiej.24.1.6.

Full text

Abstract:

Many problems, in diverse areas of science and engineering, involve the solution of largescale sparse systems of linear equations. In most of these scenarios, they are also a computational bottleneck, and therefore their efficient solution on parallel architectureshas motivated a tremendous volume of research.This dissertation targets the use of GPUs to enhance the performance of the solution of sparse linear systems using iterative methods complemented with state-of-the-art preconditioned techniques. In particular, we study ILUPACK, a package for the solution of sparse linear systems via Krylov subspace methods that relies on a modern inverse-based multilevel ILU (incomplete LU) preconditioning technique.We present new data-parallel versions of the preconditioner and the most important solvers contained in the package that significantly improve its performance without affecting its accuracy. Additionally we enhance existing task-parallel versions of ILUPACK for shared- and distributed-memory systems with the inclusion of GPU acceleration. The results obtained show a sensible reduction in the runtime of the methods, as well as the possibility of addressing large-scale problems efficiently.

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Multilevel Krylov Subspace Splitting'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles