The cyclic reduction algorithm: from Poisson equation to stochastic processes and beyond

Cyclic reduction is an algorithm invented by G. H. Golub and R. W. Hockney in the mid 1960s for solving linear systems related to the finite differences discretization of the Poisson equation over a rectangle. Among the algorithms of Gene Golub, it is one of the most versatile and powerful ever created. Recently, it has been applied to solve different problems from different applicative areas. In this paper we survey the main features of cyclic reduction, relate it to properties of analytic functions, recall its extension to solving more general finite and infinite linear systems, and different kinds of nonlinear matrix equations, including algebraic Riccati equations, with applications to Markov chains, queueing models and transport theory. Some new results concerning the convergence properties of cyclic reduction and its applicability are proved under very weak assumptions. New formulae for overcoming breakdown are provided.     

On a system of difference equations arising in the cyclic reduction

Cyclic reduction is a powerful technique in numerical linear algebra for solving tridiagonal systems. It can be classified in the class of divide and conquer methods. Some of its surprising properties have been studied recently essentially in the case of diagonally dominant matrices. In this paper the case of Toeplitz matrices will be considered. A complete analysis of the properties of the cyclic reduction will be done by studing an associate system of nonlinear difference equations.     

Solving stable generalized Lyapunov equations with the matrix sign function

We investigate the numerical solution of the stable generalized Lyapunov equation via the sign function method. This approach has already been proposed to solve standard Lyapunov equations in several publications. The extension to the generalized case is straightforward. We consider some modifications and discuss how to solve generalized Lyapunov equations with semidefinite constant term for the Cholesky factor. The basic computational tools of the method are basic linear algebra operations that can be implemented efficiently on modern computer architectures and in particular on parallel computers. Hence, a considerable speed-up as compared to the Bartels–Stewart and Hammarling methods is to be expected. We compare the algorithms by performing a variety of numerical tests.     

Systems of matrix rational differential equations arising in connection with linear stochastic systems with Markovian jumping

In this paper, a class of systems of matrix nonlinear differential equations containing as particular cases the systems of coupled Riccati differential equations arising in connection with control of some linear stochastic systems is considered.The system of differential equations considered in this paper are converted in a suitable nonlinear differential equation on a finite-dimensional Hilbert space adequately choosen.This allows us to use the positivity properties of the linear evolution operator defined by the linear differential equations of Lyapunov type.Our aim is to investigate properties of stabilizing and bounded solutions of the considered differential equations and to obtain some conditions ensuring the existence of such solutions.Conditions providing the existence of a maximal solution (minimal solution respectively) with respect to some classes of global solutions are presented. It is shown that if the coefficients of the equations are periodic functions all these special solutions (stabilizing, maximal, minimal) are periodic functions, too.Whenever possible the probabilistic arguments were avoided and so the results proved in the paper appear as results in the field of differential equations with interest in themselves.     

Efficient algorithms for generalized algebraic Bernoulli equations based on the matrix sign function

We investigate the solution of large-scale generalized algebraic Bernoulli equations as those arising in control and systems theory. Here, we discuss algorithms based on a generalization of the Newton iteration for the matrix sign function. The algorithms are easy to parallelize and provide an efficient numerical tool to solve large-scale problems. Both the accuracy and the parallel performance of our implementations on a cluster of Intel Xeon processors are reported.      

A preconditioned low‐rank CG method for parameter‐dependent Lyapunov matrix equations

This paper is concerned with the numerical solution of symmetric large‐scale Lyapunov equations with low‐rank right‐hand sides and coefficient matrices depending on a parameter. Specifically, we consider the situation when the parameter dependence is sufficiently smooth, and the aim is to compute solutions for many different parameter samples. On the basis of existing results for Lyapunov equations and parameter‐dependent linear systems, we prove that the tensor containing all solution samples typically allows for an excellent low multilinear rank approximation. Stacking all sampled equations into one huge linear system, this fact can be exploited by combining the preconditioned CG method with low‐rank truncation. Our approach is flexible enough to allow for a variety of preconditioners based, for example, on the sign function iteration or the alternating direction implicit method. Copyright © 2013 John Wiley & Sons, Ltd.     

On the Brown–Shields conjecture for cyclicity in the Dirichlet space

Let be the Dirichlet space, namely the space of holomorphic functions on the unit disk whose derivative is square-integrable. We establish a new sufficient condition for a function to be cyclic, i.e. for to be dense in . This allows us to prove a special case of the conjecture of Brown and Shields that a function is cyclic in iff it is outer and its zero set (defined appropriately) is of capacity zero.