Block Krylov Subspace Methods for Solving Large Sylvester Equations

In the present paper, we propose block Krylov subspace methods for solving the Sylvester matrix equation AX–XB=C. We first consider the case when A is large and B is of small size. We use block Krylov subspace methods such as the block Arnoldi and the block Lanczos algorithms to compute approximations to the solution of the Sylvester matrix equation. When both matrices are large and the right-hand side matrix is of small rank, we will show how to extract low-rank approximations. We give some theoretical results such as perturbation results and bounds of the norm of the error. Numerical experiments will also be given to show the effectiveness of these block methods.     

关于“求解加权线性最小二乘问题的一类预处理GAOR方法”一文的注记

在"求解加权线性最小二乘问题的一类预处理GAOR方法"一文中,作者提出了求解加权线性最小二乘问题等价$2\times 2$块线性系统的一类预处理GAOR方法,并给出了几个比较定理来说明新提出预处理GAOR方法的优越性.本文我们将指出该文中几个比较定理的不完善之处和证明的错误之处,并给出正确的证明.     

Adaptive algebraic smoothers

This paper will present a new method of adaptively constructing block iterative methods based on Local Sensitivity Analysis (LSA). The method can be used in the context of geometric and algebraic multigrid methods for constructing smoothers, and in the context of Krylov methods for constructing block preconditioners. It is suitable for both constant and variable coefficient problems. Furthermore, the method can be applied to systems arising from both scalar and coupled system partial differential equations (PDEs), as well as linear systems that do not arise from PDEs. The simplicity of the method will allow it to be easily incorporated into existing multigrid and Krylov solvers while providing a powerful tool for adaptively constructing methods tuned to a problem.     

Dealing with linear dependence during the iterations of the restarted block Lanczos methods

The Lanczos method can be generalized to block form to compute multiple eigenvalues without the need of any deflation techniques. The block Lanczos method reduces a general sparse symmetric matrix to a block tridiagonal matrix via a Gram–Schmidt process. During the iterations of the block Lanczos method an off-diagonal block of the block tridiagonal matrix may become singular, implying that the new set of Lanczos vectors are linearly dependent on the previously generated vectors. Unlike the single vector Lanczos method, this occurrence of linearly dependent vectors may not imply an invariant subspace has been computed. This difficulty of a singular off-diagonal block is easily overcome in non-restarted block Lanczos methods, see [12,30]. The same schemes applied in non-restarted block Lanczos methods can also be applied in restarted block Lanczos methods. This allows the largest possible subspace to be built before restarting. However, in some cases a modification of the restart vectors is required or a singular block will continue to reoccur. In this paper we examine the different schemes mentioned in [12,30] for overcoming a singular block for the restarted block Lanczos methods, namely the restarted method reported in [12] and the Implicitly Restarted Block Lanczos (IRBL) method developed by Baglama et al. [3]. Numerical examples are presented to illustrate the different strategies discussed.     

Computing eigenvectors of block tridiagonal matrices based on twisted block factorizations

New methods for computing eigenvectors of symmetric block tridiagonal matrices based on twisted block factorizations are explored. The relation of the block where two twisted factorizations meet to an eigenvector of the block tridiagonal matrix is reviewed. Based on this, several new algorithmic strategies for computing the eigenvector efficiently are motivated and designed. The underlying idea is to determine a good starting vector for an inverse iteration process from the twisted block factorizations such that a good eigenvector approximation can be computed with a single step of inverse iteration.     

Spectral analysis of the affine graph over the finite ring

We apply two methods to the block diagonalization of the adjacency matrix of the Cayley graph defined on the affine group. The affine group will be defined over the finite ring Z/pⁿZ. The method of irreducible representations will allow us to find nontrivial eigenvalue bounds for two different graphs. One of these bounds will result in a family of Ramanujan graphs. The method of covering graphs will be used to block diagonalize the affine graphs using a Galois group of graph automorphisms. In addition, we will demonstrate the method of covering graphs on a generalized version of the graphs of Lubotzky et al. [A. Lubotzky, R. Phillips, P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988) 261-277].     

Look-ahead methods for block Hankel systems

In this paper, the updating formulas used by three look-ahead methods for solving Hankel systems are generalized to the square block case. Each of the original methods was described in the literature using the terminology of different but strongly related fields: formal orthogonal polynomials, Padé approximants, structured matrices. This paper gives several of these connections generalized to the block case and shows that each viewpoint has its own merits.     

A deflated conjugate gradient method for multiple right hand sides and multiple shifts

We consider the task of computing solutions of linear systems that only differ by a shift with the identity matrix as well as linear systems with several different right-hand sides. In the past, Krylov subspace methods have been developed which exploit either the need for solutions to multiple right-hand sides (e.g. deflation type methods and block methods) or multiple shifts (e.g. shifted CG) with some success. In this paper we present a block Krylov subspace method which, based on a block Lanczos process, exploits both features—shifts and multiple right-hand sides—at once. Such situations arise, for example, in lattice quantum chromodynamics (QCD) simulations within the Rational Hybrid Monte Carlo (RHMC) algorithm. We present numerical evidence that our method is superior compared to applying other iterative methods to each of the systems individually as well as, in typical situations, to shifted or block Krylov subspace methods.     

Block s‐step Krylov iterative methods

Block (including s‐step) iterative methods for (non)symmetric linear systems have been studied and implemented in the past. In this article we present a (combined) block s‐step Krylov iterative method for nonsymmetric linear systems. We then consider the problem of applying any block iterative method to solve a linear system with one right‐hand side using many linearly independent initial residual vectors. We present a new algorithm which combines the many solutions obtained (by any block iterative method) into a single solution to the linear system. This approach of using block methods in order to increase the parallelism of Krylov methods is very useful in parallel systems. We implemented the new method on a parallel computer and we ran tests to validate the accuracy and the performance of the proposed methods. It is expected that the block s‐step methods performance will scale well on other parallel systems because of their efficient use of memory hierarchies and their reduction of the number of global communication operations over the standard methods. Copyright © 2009 John Wiley & Sons, Ltd.     

On Preconditioning of Incompressible Non-Newtonian Flow Problems

This paper deals with fast and reliable numerical solution methods for the incompressible non-Newtonian Navier-Stokes equations. To handle the nonlinearity of the governing equations, the Picard and Newton methods are used to linearize these coupled partial differential equations. For space discretization we use the finite element method and utilize the two-by-two block structure of the matrices in the arising algebraic systems of equations. The Krylov subspace iterative methods are chosen to solve the linearized discrete systems and the development of computationally and numerically efficient preconditioners for the two-by-two block matrices is the main concern in this paper. In non-Newtonian flows, the viscosity is not constant and its variation is an important factor that affects the performance of some already known preconditioning techniques. In this paper we examine the performance of several preconditioners for variable viscosity applications, and improve them further to be robust with respect to variations in viscosity.     

A methodology for modelling travel distances by Bias estimation

Round norms τl _p, p ∈ (1,2] and block norms have been utilised for modelling actual distances in transportation networks. A geometric setting will permit the establishment of a relationship between bias of the road network distance and trajectory deviations, which will be used to separate the set of origin-destination pairs into two samples and also to analyse each sample using regression, thus obtaining several types of estimators. What will be demonstrated in this paper is that these functions can be combined through either a weighted sum, or by means of the introduction of the expected distance concept applied to the bias, to obain distance predicting functions for the region considered.     

Compact block boundary value methods for semi-linear delay-reaction–diffusion equations with algebraic constraints

In the present paper, we study a class of linear approximation methods for solving semi-linear delay-reaction–diffusion equations with algebraic constraint (SDEACs). By combining a fourth-order compact difference scheme with block boundary value methods (BBVMs), a class of compact block boundary value methods (CBBVMs) for SDEACs are suggested. It is proved under some suitable conditions that the CBBVMs are convergent of order 4 in space and order p in time, where p is the local order of the used BBVMs, and are globally stable. With several numerical experiments for Fisher equation with delay and algebraic constraint, the computational effectiveness and theoretical results of CBBVMs are further illustrated.     

线性块SOR二级迭代法的收敛性质

内迭代次数充分大时,求解非奇异线性方程组的块SOR二级迭代法与经典的块SOR方法有相同的收敛性和大致相等的收敛速度.因此,用于块SOR方法有效的松弛因子,同样可有效地用于块SOR二级迭代法.     

Block and joint ℋ︁-matrix preconditioners for the Oseen equations

For saddle point problems in fluid dynamics, many preconditioners in the literature exploit the block structure of the problem to construct block diagonal or block triangular preconditioners. The performance of such preconditioners depends on whether fast, approximate solvers for the linear systems on the block diagonal as well as for the Schur complement are available. We will construct these efficient preconditioners using hierarchical matrix techniques in which fully populated matrices are approximated by blockwise low rank approximations. We will compare such block preconditioners with those obtained through a completely different approach where the given block structure is not used but a domain-decomposition based ℋ︁-LU factorization is constructed for the complete system matrix. Preconditioners resulting from these two approaches will be discussed and compared through numerical results. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Multi-period stochastic portfolio optimization: Block-separable decomposition

We consider a multiperiod stochastic programming recourse model for stock portfolio optimization. The presence of various risk and policy constraints leads to significant period-by-period linkage in the model. Furthermore, the dimensionality of the model is large due to many securities under consideration. We propose exploiting block separable recourse structure as well as methods of inducing such structure within nested L-shaped decomposition. We test the model and solution methodology with a base consisting of the Standard & Poor 100 stocks and experiment with several variants of the block separable technique. These are then compared to the standard nested period-by-period decomposition algorithm. It turns out that for financial optimization models of the kind that are discussed in this paper, significant computational efficiencies can be gained with the proposed methodology.     

Distributing the Encryption and Decryption of a Block Cipher

In threshold cryptography, the goal is to distribute the computation of basic cryptographic primitives across a number of nodes in order to relax trust assumptions on individual nodes, as well as to introduce a level of fault-tolerance against node compromise. Most threshold cryptography has previously looked at the distribution of public key primitives, particularly threshold signatures and threshold decryption mechanisms. In this paper, we look at the application of threshold cryptography to symmetric primitives, and in particular the encryption or decryption of a symmetric key block cipher. We comment on some previous work in this area and then propose a model for shared encryption / decryption of a block cipher. We will present several approaches to enable such systems and will compare them.AMS classification: 94A60, 94A62, 68P25     

求解时谐涡流模型鞍点问题的分块交替分裂隐式迭代算法的改进

分块交替分裂隐式迭代方法是求解具有鞍点结构的复线性代数方程组的一类高效迭代法.本文通过预处理技巧得到原方法的一种加速改进方法,称之为预处理分块交替分裂隐式迭代方法·理论分析给出了新方法的收敛性结果.对于一类时谐涡旋电流模型问题,我们给出了若干满足收敛条件的迭代格式.数值实验验证了新型算法是对原方法的有效改进.     

基于FLAC-3D砂岩块体超低摩擦鞭梢效应研究北大核心CSCD

随着矿山开采深度的持续增加,深部岩体力学行为呈现出新形式、新特征.广泛应用于建筑行业的鞭梢效应与深部岩体部分动力响应现象极为相似.故从结构特征出发,以砂岩块体为研究对象,工作块体(水平冲击作用块体)水平位移及加速度为参考指标,通过试验及FLAC-3D数值模拟计算的方式,探究工作块体“位置”及“尺寸”对其超低摩擦鞭梢效应影响机制.研究表明:系统产生超低摩擦鞭梢效应的难易程度与工作块体尺寸密切相关,模拟中工作块体边长为标准块体(边长100 mm立方体)边长2/5时,系统结构诱发超低摩擦鞭梢效应尤其显著;在一定范围内,工作块体所处位置距扰动源越远,超低摩擦鞭梢效应强度越大,当超过这一范围时,则会出现减小趋势,即超低摩擦鞭梢效应强度随工作块体与震源块体间距离呈先增后减关系.     

一类T单调算子障碍问题的块单调迭代法

本文对一类T单调算子的障碍问题提出了几个块迭代法．所得的迭代序列为上解序列和下解序列,它们均单调收敛于问题的准确解,本文建立了这些算法的比较定理．     

Preconditioning discretizations of systems of partial differential equations

This survey paper is based on three talks given by the second author at the London Mathematical Society Durham Symposium on Computational Linear Algebra for Partial Differential Equations in the summer of 2008. The main focus will be on an abstract approach to the construction of preconditioners for symmetric linear systems in a Hilbert space setting. Typical examples that are covered by this theory are systems of partial differential equations which correspond to saddle point problems. We will argue that the mapping properties of the coefficient operators suggest that block diagonal preconditioners are natural choices for these systems. To illustrate our approach a number of examples will be considered. In particular, parameter‐dependent systems arising in areas like incompressible flow, linear elasticity, and optimal control theory will be studied. The paper contains analysis of several models which have previously been discussed in the literature. However, here each example is discussed with reference to a more unified abstract approach. Copyright © 2010 John Wiley & Sons, Ltd.