Compress‐and‐restart block Krylov subspace methods for Sylvester matrix equations

Block Krylov subspace methods (KSMs) comprise building blocks in many state‐of‐the‐art solvers for large‐scale matrix equations as they arise, for example, from the discretization of partial differential equations. While extended and rational block Krylov subspace methods provide a major reduction in iteration counts over polynomial block KSMs, they also require reliable solvers for the coefficient matrices, and these solvers are often iterative methods themselves. It is not hard to devise scenarios in which the available memory, and consequently the dimension of the Krylov subspace, is limited. In such scenarios for linear systems and eigenvalue problems, restarting is a well‐explored technique for mitigating memory constraints. In this work, such restarting techniques are applied to polynomial KSMs for matrix equations with a compression step to control the growing rank of the residual. An error analysis is also performed, leading to heuristics for dynamically adjusting the basis size in each restart cycle. A panel of numerical experiments demonstrates the effectiveness of the new method with respect to extended block KSMs.     

Optimal control of delay systems via block pulse functions

The concept of coefficient shift matrix is introduced to represent delay variables in block pulse series. The optimal control of a linear delay system with quadratic performance index is then studied via block pulse functions, which convert the problems into the minimization of a quadratic form with linear algebraic equation constraints. The solution of the two-point boundary-value problem with both delay and advanced arguments is circumvented. The control variable obtained is piecewise constant.     

Branch and bound algorithm for a transfer line design problem: Stations with sequentially activated multi-spindle heads

In this paper, a new transfer line balancing problem is considered. The main difference from the simple assembly line balancing problem is that the operations are grouped into blocks (batches). All the operations of the same block are carried out simultaneously by one piece of equipment (multi-spindle head). Nevertheless, the blocks assigned to the same workstation are executed in series. The line cost consists of the sum of block and workstation costs. At the considered line design stage, the set of all available blocks is given. The aim is to find a subset from the given set of available blocks and to find a partition of this subset to workstations such that each operation is executed once and the line cost is minimal while all the precedence, cycle time, and compatibility (operation inclusion and block exclusion) constraints are respected. A new lower bound based on solving a special set partitioning problem is presented and a branch and bound algorithm is developed. The experimental results prove the quality of the lower bound and applicability of the suggested branch and bound algorithm for medium sized industrial cases.     

Asynchronous pole assignment for linear systems with blocks of incomplete rank

We consider a linear periodic control system with constant matrix multiplying the control in the critical case under the assumption that the mean of the coefficient matrix is block triangular and some blocks of its nonstationary part have incomplete column rank. A linear state feedback control periodic with the same period as the system itself is considered. We obtain necessary and sufficient conditions for the solvability of the asynchronous pole assignment problem, that is, the problem of finding a feedback factor such that the closed-loop system has a strongly irregular periodic solution with desired frequencies.     

Balancing modular transfer lines with serial-parallel activation of spindle heads at stations

The paper deals with an as yet unexplored combinatorial optimization problem concerning balancing complex transfer lines in the machining/process environment. In contrast to similar problems for assembly lines, in transfer line balancing, tasks are grouped into blocks. All tasks of each block are executed simultaneously (in parallel) by one piece of equipment (spindle head). For the transfer lines considered in this paper, spindle heads at each station are activated in serial-parallel order. The set of all available spindle heads is known beforehand. Precedence, cycle time, compatibility, and parallelism constraints for the blocks and tasks are given. The line investment cost is estimated by the sum of block and station costs. The problem is to assign all tasks (using the available blocks) such that all constraints are respected and line investment cost is at a minimum. This paper focuses on solving the problem via a branch-and-bound algorithm. An approach for obtaining an efficient lower bound is offered, based on a reduction of the initial problem to a set partitioning problem. Computational experiments reveal that the proposed approach is efficient mathematically and can be used to solve practical transfer line design problems of a medium size.     

Preconditioning of two-by-two block matrix systems with square matrix blocks,with applications

Two-by-two block matrices of special form with square matrix blocks arise in important applications, such as in optimal control of partial differential equations and in high order time integration methods.Two solution methods involving very efficient preconditioned matrices, one based on a Schur complement reduction of the given system and one based on a transformation matrix with a perturbation of one of the given matrix blocks are presented. The first method involves an additional inner solution with the pivot matrix block but gives a very tight condition number bound when applied for a time integration method. The second method does not involve this matrix block but only inner solutions with a linear combination of the pivot block and the off-diagonal matrix blocks.Both the methods give small condition number bounds that hold uniformly in all parameters involved in the problem, i.e. are fully robust. The paper presents shorter proofs, extended and new results compared to earlier publications.     

A special case of transfer lines balancing by graph approach

A balancing problem for paced production lines with workstations in series and blocks of parallel operations at the workstations is considered. Operations of each workstation are partitioned into blocks. All operations of the same block are performed simultaneously by one spindle head. All blocks of the same workstation are also executed simultaneously. The relations of the necessity of executing some operations at the same workstation, the possibility of combining the blocks at the same workstation as well as precedence constraints are given. The operation time of the workstation is the maximal value among operation times of its blocks. The line cycle time is the maximal workstation time. The problem is to choose blocks from a given set and allocate them to workstations in such a way that (i) all the operations are assigned, (ii) the above constraints are satisfied, (iii) a given cycle time is not exceeded, and (iv) the line cost is minimal. A method for solving the problem is based on its transformation to a constrained shortest path problem.     

Preconditioning techniques for an image deblurring problem

In this paper, we consider the solution of a large linear system of equations, which is obtained from discretizing the Euler–Lagrange equations associated with the image deblurring problem. The coefficient matrix of this system is of the generalized saddle point form with high condition number. One of the blocks of this matrix has the block Toeplitz with Toeplitz block structure. This system can be efficiently solved using the minimal residual iteration method with preconditioners based on the fast Fourier transform. Eigenvalue bounds for the preconditioner matrix are obtained. Numerical results are presented. Copyright © 2016 John Wiley & Sons, Ltd.     

Matrix correction of a dual pair of improper linear programming problems

A matrix is sought that solves a given dual pair of systems of linear algebraic equations. Necessary and sufficient conditions for the existence of solutions to this problem are obtained, and the form of the solutions is found. The form of the solution with the minimal Euclidean norm is indicated. Conditions for this solution to be a rank one matrix are examined. On the basis of these results, an analysis is performed for the following two problems: modifying the coefficient matrix for a dual pair of linear programs (which can be improper) to ensure the existence of given solutions for these programs, and modifying the coefficient matrix for a dual pair of improper linear programs to minimize its Euclidean norm. Necessary and sufficient conditions for the solvability of the first problem are given, and the form of its solutions is described. For the second problem, a method for the reduction to a nonlinear constrained minimization problem is indicated, necessary conditions for the existence of solutions are found, and the form of solutions is described. Numerical results are presented.     

Asynchronous pole assignment for linear systems with independent blocks

We consider a linear periodic control system with linearly independent column bases of the blocks of the coefficient matrix, which has zero mean value and admits a block triangular representation. For the case of a linear state feedback control periodic with the same period as the system itself, we obtain necessary and sufficient conditions for the solvability of the asynchronous pole assignment problem, i.e., the problem of finding a feedback coefficient such that the closed-loop system has a strongly irregular periodic solution with the desired frequencies.     

Rotated block triangular preconditioning based on PMHSS

Based on the PMHSS preconditioning matrix, we construct a class of rotated block triangular preconditioners for block two-by-two matrices of real square blocks, and analyze the eigen-properties of the corresponding preconditioned matrices. Numerical experiments show that these rotated block triangular preconditioners can be competitive to and even more efficient than the PMHSS pre-conditioner when they are used to accelerate Krylov subspace iteration methods for solving block two-by-two linear systems with coefficient matrices possibly of nonsymmetric sub-blocks.     

On order‐reducible sinc discretizations and block‐diagonal preconditioning methods for linear third‐order ordinary differential equations

By introducing a variable substitution, we transform the two‐point boundary value problem of a third‐order ordinary differential equation into a system of two second‐order ordinary differential equations (ODEs). We discretize this order‐reduced system of ODEs by both sinc‐collocation and sinc‐Galerkin methods, and average these two discretized linear systems to obtain the target system of linear equations. We prove that the discrete solution resulting from the linear system converges exponentially to the true solution of the order‐reduced system of ODEs. The coefficient matrix of the linear system is of block two‐by‐two structure, and each of its blocks is a combination of Toeplitz and diagonal matrices. Because of its algebraic properties and matrix structures, the linear system can be effectively solved by Krylov subspace iteration methods such as GMRES preconditioned by block‐diagonal matrices. We demonstrate that the eigenvalues of certain approximation to the preconditioned matrix are uniformly bounded within a rectangle on the complex plane independent of the size of the discretized linear system, and we use numerical examples to illustrate the feasibility and effectiveness of this new approach. Copyright © 2013 John Wiley & Sons, Ltd.     

Parallel block preconditioning based on SSOR and MILU

Two kinds of parallel preconditioners for the solution of large sparse linear systems which arise from the 2-D 5-point finite difference discretization of a convection-diffusion equation are introduced. The preconditioners are based on the SSOR or MILU preconditioners and can be implemented on parallel computers with distributed memories. One is the block preconditioner, in which the interface components of the coefficient matrix between blocks are ignored to attain parallelism in the forward-backward substitutions. The other is the modified block preconditioner, in which the block preconditioner is modified by taking the interface components into account. The effect of these preconditioners on the convergence of preconditioned iterative methods and timing results on the parallel computer (Cenju) are presented.     

块循环矩阵方程组的新算法

1　基本概念形如 A=a1 a2 … a Na N a1 … a N- 1?彙?廰2 a3 … a1的矩阵称为由 a1 ,a2 ,… ,a N 生成的循环矩阵 .力学和工程中的轴对称结构的计算产生上述循环矩阵 [2 - 3] .以循环矩阵A为系数矩阵的方程组 ,称为循环矩阵方程组 .已有的求解循环矩阵方程组的办法主要是各种迭代法 ,如递推法及 SOR,SSOR,SAOR超松弛迭代法[2 - 6] 等 .定义 1　形如A =A1 A2 … ANAN A1… AN- 1?彙?廇2 A3… A1　 (Ai,i =1 ,2 ,… ,N为 m阶矩阵 )的矩阵称为由 A1 ,A2 ,… ,AN 生成的块循环矩阵 .定义 2　系数矩阵 A为块循环矩阵的方程组AX …     

Control of asynchronous spectrum of linear systems with a two-sided dependence of blocks of complete column rank

We consider a linear periodic control system with a two-sided dependence of blocks of complete column rank in the nonstationary component of the coefficient matrix in the critical case. In this case, the nontrivial intersection of vector subspaces formed by linear spans of the columns in the blocks can be arbitrary. We assume that the control is given in the form of feedback linear in the state variables and is periodic with the period of the system. We derive necessary and sufficient conditions for the solvability of the control problem for the asynchronous spectrum, that is, the problem of finding a feedback coefficient such that the closed system has a strongly irregular periodic solution with the desired frequencies.     

A method for verifying the accuracy of numerical solutions of symmetric saddle point linear systems

A fast numerical verification method is proposed for evaluating the accuracy of numerical solutions for symmetric saddle point linear systems whose diagonal blocks of the coefficient matrix are semidefinite matrices. The method is based on results of an algebraic analysis of a block diagonal preconditioning. Some numerical experiments are present to illustrate the usefulness of the method.     

A robust and efficient proposal for solving linear systems arising in interior-point methods for linear programming

We introduce an efficient and robust proposal for solving linear systems arising at each iteration of primal-dual interior-point methods for linear programming. Our proposal is based on the stable system presented by Gonzalez-Lima et al. (Comput. Opt. Appl. 44:213–247, 2009). Using similar techniques as those employed in the splitting preconditioner introduced by Oliveira and Sorensen (Linear Algebra Appl. 394:1–24, 2005) we are able to express the stable system matrix in block form such that the diagonal blocks are nonsingular diagonal matrices and the off-diagonal blocks are matrices close to zero when the iterates are close to the solution set of the linear programming problem. For degenerate problems a perturbation of the diagonal is added. We use a low-cost fixed iterative method to solve this system. Numerical experiments have shown that our approach leads to very accurate solutions for the linear programming problem.     

A tearing-based hybrid parallel sparse linear system solver

We propose a hybrid sparse system solver for handling linear systems using algebraic domain decomposition-based techniques. The solver consists of several stages. The first stage uses a reordering scheme that brings as many of the largest matrix elements as possible closest to the main diagonal. This is followed by partitioning the coefficient matrix into a set of overlapped diagonal blocks that contain most of the largest elements of the coefficient matrix. The only constraint here is to minimize the size of each overlap. Separating these blocks into independent linear systems with the constraint of matching the solution parts of neighboring blocks that correspond to the overlaps, we obtain a balance system. This balance system is not formed explicitly and has a size that is much smaller than the original system. Our novel solver requires only a one-time factorization of each diagonal block, and in each outer iteration, obtaining only the upper and lower tips of a solution vector where the size of each tip is equal to that of the individual overlap. This scheme proves to be scalable on clusters of nodes in which each node has a multicore architecture. Numerical experiments comparing the scalability of our solver with direct and preconditioned iterative methods are also presented.     

Optimisation of multi-position machines and transfer lines

A new optimisation problem for design of multi-position machines and automatic transfer lines is considered. To reduce the number of pieces of equipment, machining operations are grouped into blocks. The operations of the same block are performed simultaneously by one piece of equipment (multi-spindle head). At the studied design stage, constraints related to the design of blocks and workstations, as well as precedence constraints for operations are known. The problem consists in an optimal grouping of the operations into blocks minimizing the total number of blocks and workstations while reaching a given cycle time (productivity). A constrained shortest path algorithm is developed and tested.     

An implementation of a parallel primal-dual interior point method for block-structured linear programs

An implementation of the primal-dual predictor-corrector interior point method is specialized to solve block-structured linear programs with side constraints. The block structure of the constraint matrix is exploited via parallel computation. The side constraints require the Cholesky factorization of a dense matrix, where a method that exploits parallelism for the dense Cholesky factorization is used. For testing, multicommodity flow problems were used. The resulting implementation is 65%–90% efficient, depending on the problem instance. For a problem with K commodities, an approximate speedup for the interior point method of 0.8K is realized.