Application of preconditioned block BiCGGR to the Wilson-Dirac equation with multiple right-hand sides in lattice QCD

There exist two major problems in application of the conventional block BiCGSTAB method to the O(a)-improved Wilson-Dirac equation with multiple right-hand sides: One is the deviation between the true and the recursive residuals. The other is the convergence failure observed at smaller quark masses for enlarged number of the right-hand sides. The block BiCGGR algorithm which was recently proposed by the authors succeeds in solving the former problem. In this article we show that a preconditioning technique allows us to improve the convergence behavior for increasing number of the right-hand sides.     

Solution of the Dirac equation in lattice QCD using a domain decomposition method

Efficient algorithms for the solution of partial differential equations on parallel computers are often based on domain decomposition methods. Schwarz preconditioners combined with standard Krylov space solvers are widely used in this context, and such a combination is shown here to perform very well in the case of the Wilson-Dirac equation in lattice QCD. In particular, with respect to even-odd preconditioned solvers, the communication overhead is significantly reduced, which allows the computational work to be distributed over a large number of processors with only small parallelization losses.     

A parallel linear solver for multilevel Toeplitz systems with possibly several right-hand sides

A Toeplitz matrix has constant diagonals; a multilevel Toeplitz matrix is defined recursively with respect to the levels by replacing the matrix elements with Toeplitz blocks. Multilevel Toeplitz linear systems appear in a wide range of applications in science and engineering. This paper discusses an MPI implementation for solving such a linear system by using the conjugate gradient algorithm. The implementation techniques can be generalized to other iterative Krylov methods besides conjugate gradient. These techniques include the use of an arbitrary dimensional process grid for handling the multilevel Toeplitz structure, a communication-hiding approach for performing matrix–vector multiplications, the incorporation of multilevel circulant preconditioning for accelerating convergence, an efficient orthogonalization manager for detecting linear dependence in block iterations, and an algorithmic rearrangement to eliminate all-reduce synchronizations. The combined use of these techniques leads to a scalable solver for large multilevel Toeplitz systems, possibly with several right-hand sides. We show experimental results on matrices of size up to the order of one billion with nearly perfect scaling by using up to 1024 MPI processes. We also demonstrate an application of the solver in parameter estimation for analyzing large-scale climate data.     

三维热传导方程的Krylov子空间方法并行分析

热传导方程在地下水流动数值模拟、油藏数值模拟等工程计算中有着广泛应用,其并行实现是加速问题求解速度、提高问题求解规模的重要手段,因此热传导方程的并行求解具有重要意义。对Krylov子空间方法中的CG和GMRES算法进行并行分析,并对不同的预处理CG算法作了比较。在Linux集群系统上,以三维热传导模型为例进行了数值实验。实验结果表明,CG算法比GMRES算法更适合建立三维热传导模型的并行求解。此外,CG算法与BJACOBI预条件子的整合在求解该热传导模型时,其并行程序具有良好的加速比和效率。因此,采用BJACOBI预处理技术的CG算法是一种较好的求解三维热传导模型的并行方案。     

A nested Krylov subspace method to compute the sign function of large complex matrices

We present an acceleration of the well-established Krylov–Ritz methods to compute the sign function of large complex matrices, as needed in lattice QCD simulations involving the overlap Dirac operator at both zero and nonzero baryon density. Krylov–Ritz methods approximate the sign function using a projection on a Krylov subspace. To achieve a high accuracy this subspace must be taken quite large, which makes the method too costly. The new idea is to make a further projection on an even smaller, nested Krylov subspace. If additionally an intermediate preconditioning step is applied, this projection can be performed without affecting the accuracy of the approximation, and a substantial gain in efficiency is achieved for both Hermitian and non-Hermitian matrices. The numerical efficiency of the method is demonstrated on lattice configurations of sizes ranging from 4⁴ to 10⁴, and the new results are compared with those obtained with rational approximation methods.     

Preconditioning the solution of the time-dependent neutron diffusion equation by recycling Krylov subspaces

Spectral preconditioners are based on the fact that the convergence rate of the Krylov subspace methods is improved if the eigenvalues of the smallest magnitude of the system matrix are ‘removed’. In this paper, two preconditioning strategies are studied to solve a set of linear systems associated with the numerical integration of the time-dependent neutron diffusion equation. Both strategies can be implemented using the matrix–vector product as the main operation and succeed at reducing the total number of iterations needed to solve the set of systems.     

A novel class of block methods based on the block AA T-Lanczos bi-orthogonalization process for matrix equations

In this paper, we introduce a block AA ^T-Lanczos bi-orthogonalization process. Based on this new process, the block bi-conjugate residual (Bl-BCR) method is derived, which is also a generalization of bi-conjugate residual method. In order to accelerate the rate of convergence, we generate a stabilized and more smoothly converging variant of Bl-BCR using formal matrix-valued orthogonal polynomials. Finally, numerical experiments illustrate the effectiveness of these block methods.     

Application of the incomplete Cholesky factorization preconditioned Krylov subspace method to the vector finite element method for 3-D electromagnetic scattering problems

The incomplete Cholesky (IC) factorization preconditioning technique is applied to the Krylov subspace methods for solving large systems of linear equations resulted from the use of edge-based finite element method (FEM). The construction of the preconditioner is based on the fact that the coefficient matrix is represented in an upper triangular compressed sparse row (CSR) form. An efficient implementation of the IC factorization is described in detail for complex symmetric matrices. With some ordering schemes our IC algorithm can greatly reduce the memory requirement as well as the iteration numbers. Numerical tests on harmonic analysis for plane wave scattering from a metallic plate and a metallic sphere coated by a lossy dielectric layer show the efficiency of this method.     

Approximation of matrix operators applied to multiple vectors

In this paper we propose a numerical method for approximating the product of a matrix function with multiple vectors by Krylov subspace methods combined with a QR$QR$ decomposition of these vectors. This problem arises in the implementation of exponential integrators for semilinear parabolic problems. We will derive reliable stopping criteria and we suggest variants using up- and downdating techniques. Moreover, we show how Ritz vectors can be included in order to speed up the computation even further. By a number of numerical examples, we will illustrate that the proposed method will reduce the total number of Krylov steps significantly compared to a standard implementation if the vectors correspond to the evaluation of a smooth function at certain quadrature points.     

A bifurcation method for solving multiple positive solutions to the boundary value problem of the Henon equation on a unit disk

Three algorithms based on the bifurcation theory are proposed to compute the O(2) symmetric positive solutions to the boundary value problem of the Henon equation on the unit disk. Taking l in the Henon equation as a bifurcation parameter, the symmetry-breaking bifurcation point on the branch of the O(2) symmetric positive solutions is found via the extended systems. Finally, other symmetric positive solutions are computed by the branch switching method based on the Lyapunov-Schmidt reduction.     

Iterative computational approach to the solution of the Hamilton-Jacobi-Bellman-Isaacs equation in nonlinear optimal control

In this paper, iterative or successive approximation methods for the Hamilton-Jacobi-Bellman-Isaacs equations (HJBIEs) arising in both deterministic and stochastic optimal control for affine nonlinear systems are developed. Convergence of the methods are established under fairly mild assumptions, and examples are solved to demonstrate the effectiveness of the methods. However, the results presented in the paper are preliminary, and do not yet imply in anyway that the solutions computed will be stabilizing. More improvements and experimentation will be required before a satisfactory algorithm is developed.