Search

In this paper, we study a variation of the HSS iteration method which was first formulated by Bai et al. in 2003. This variation is similar to that of Kellogg's variation of the Peaceman-Radford method. [ABSTRACT FROM AUTHOR]

For an elliptic curve E defined over a number field K, the heuristic density of the set of primes of K for which E has cyclic reduction is given by an inclusion–exclusion sum δ E / K involving the degrees of the m-division fields K m of E over K. This density can be proved to be correct under assumption of GRH. For E without complex multiplication (CM), we show that δ E / K is the product of an explicit non-negative rational number reflecting the finite entanglement of the division fields of E and a universal infinite Artin-type product. For E admitting CM over K by a quadratic order O , we show that δ E / K admits a similar 'factorization' in which the Artin type product also depends on O . For E admitting CM over K ¯ by an order O ⊄ K , which occurs for K = Q , the entanglement of division fields over K is non-finite. In this case we write δ E / K as the sum of two contributions coming from the primes of K that are split and inert in O . The split contribution can be dealt with by the previous methods, the inert contribution is of a different nature. We determine the ways in which the density can vanish, and provide numerical examples of the different kinds of densities. [ABSTRACT FROM AUTHOR]

We present a robust and scalable preconditioner for the solution of large-scale linear systems that arise from the discretization of elliptic PDEs amenable to rank compression. The preconditioner is based on hierarchical low-rank approximations and the cyclic reduction method. The setup and application phases of the preconditioner achieve log-linear complexity in memory footprint and number of operations, and numerical experiments exhibit good weak and strong scalability at large processor counts in a distributed memory environment. Numerical experiments with linear systems that feature symmetry and nonsymmetry, definiteness and indefiniteness, constant and variable coefficients demonstrate the preconditioner applicability and robustness. Furthermore, it is possible to control the number of iterations via the accuracy threshold of the hierarchical matrix approximations and their arithmetic operations, and the tuning of the admissibility condition parameter. Together, these parameters allow for optimization of the memory requirements and performance of the preconditioner.

We present a robust and scalable preconditioner for the solution of large-scale linear systems that arise from the discretization of elliptic PDEs amenable to rank compression. The preconditioner is based on hierarchical low-rank approximations and the cyclic reduction method. The setup and application phases of the preconditioner achieve log-linear complexity in memory footprint and number of operations, and numerical experiments exhibit good weak and strong scalability at large processor counts in a distributed memory environment. Numerical experiments with linear systems that feature symmetry and nonsymmetry, definiteness and indefiniteness, constant and variable coefficients demonstrate the preconditioner applicability and robustness. Furthermore, it is possible to control the number of iterations via the accuracy threshold of the hierarchical matrix approximations and their arithmetic operations, and the tuning of the admissibility condition parameter. Together, these parameters allow for optimization of the memory requirements and performance of the preconditioner.

The solution of linear systems is a crucial and indispensable technique in the field of numerical analysis. Among linear system solvers, the cyclic reduction algorithm stands out for its natural inclination to parallelization. So far, the cyclic reduction has been applied primarily to linear systems with almost block diagonal matrices. Some of its variants widen the usage to almost block diagonal matrices with a last block of rows introducing a set of non-zero elements in the first group of columns. In this work, we extend cyclic reduction to matrices with additional non-zero elements below and to the right without any limitations. These matrices, called padded bordered almost block diagonal, arise from the discretization of optimal control problems featuring arbitrary boundary conditions and free parameters. Nonetheless, they also appear in two-point boundary value problems with free parameters. The proposed algorithm is based on the LU factorizations, and it is designed to be executed in parallel on multi-thread architectures. The algorithm performance is assessed through numerical experiments with different matrix sizes and threads. The computation times and speedups obtained with the parallel implementation indicate that the suggested algorithm is a robust solution for solving padded bordered almost block diagonal linear systems. Furthermore, its structure makes it suitable for the use of different matrix factorization techniques, such as QR or SVD. This flexibility enables tailored customization of the algorithm on the basis of the specific application requirements. [ABSTRACT FROM AUTHOR]

We generalize a method for avoiding GPU shared communication when dealing with a downsweep pattern. We apply this generalization to Cyclic Reduction, a tridiagonal solver with this pattern. Previously, Cyclic Reduction suffered poor performance when compared to other tridiagonal solvers on the GPU due to performance issues stemming from shared memory bandwidth bottlenecks and step-efficiency. We address this problem by applying our downsweep shared-memory communication reducing methodology. Our re-mapping also allows Cyclic Reduction to solve larger systems directly in a virtual block. By using our generalized mapping, we improve Cyclic Reduction's performance on a GPU by a factor of 3--4.5x over the original CR implementation, making it 1.5--3x faster than other GPU tridiagonal solvers.

The nonlinear matrix equation X p = R + M T (X - 1 + B) - 1 M , where p is a positive integer, M is an arbitrary n × n real matrix, R and B are symmetric positive semidefinite matrices, is considered. When p = 1 , this matrix equation is the well-known discrete-time algebraic Riccati equation (DARE), we study the convergence rate of an iterative method which was proposed in Meng and Kim (J Comput Appl Math 322:139–147, 2017). For the generalized case p ≥ 1 , a structured condition number based on the classic definition of condition number is defined and its explicit expression is obtained. Finally, we give some numerical examples to show the sharpness of the structured condition number. [ABSTRACT FROM AUTHOR]

Abstract The quadratic eigenvalue problem (QEP) (λ 2 M + λ G + K) x = 0 , with M T = M being positive definite, K T = K being negative definite and G T = − G , is associated with gyroscopic systems. In Guo (2004), a cyclic-reduction-based solvent (CRS) method was proposed to compute all eigenvalues of the above mentioned QEP. Firstly, the problem is converted to find a suitable solvent of the quadratic matrix equation (QME) M X 2 + G X + K = 0. Then using a Cayley transformation and a proper substitution, the QME is transformed into the nonlinear matrix equation (NME) Z + A T Z − 1 A = Q with A = M + K + G and Q = 2 (M − K). The problem finally can be solved by applying the CR method to obtain the maximal symmetric positive definite solution of the NME as long as the QEP has no eigenvalues on the imaginary axis or for some cases where the QEP has eigenvalues on the imaginary axis. However, when all eigenvalues of the QEP are far away from or near the origin, the Cayley transformation seems not to be the best one and the convergence rate of the CRS method proposed in Guo (2004) might be further improved. In this paper, inspired by using a doubling algorithm to solve the QME, we use a Möbius transformation instead of the Cayley transformation to present an accelerated CRS (ACRS) method for solving the QEP of gyroscopic systems. In addition, we discuss the selection strategies of optimal parameter for the ACRS method. Numerical results demonstrate the efficiency of our method. [ABSTRACT FROM AUTHOR]

Highlights • Dynamic optimization strategies are developed for parallel architectures. • Classical cyclic reductions are modified and demonstrated on structured KKT systems. • Four applications are described and demonstrated for large-scale dynamic systems. • Modified cyclic reduction has superior parallel performance for large-scale problems. Abstract Direct transcription of dynamic optimization problems, with differential-algebraic equations discretized and written as algebraic constraints, can create very large nonlinear optimization problems. When this discretized optimization problem is solved with an NLP solver, such as IPOPT, the dominant computational cost often lies in solving the linear system that generates Newton steps for the KKT system. Computational cost and memory constraints for this linear system solution raise many challenges as the system size increases. On the other hand, the linear KKT system for our dynamic optimization problem is sparse and structured, and can be permuted to form a block tridiagonal matrix. This study explores a parallel decomposition strategy for block tridiagonal systems that is based on cyclic reduction (CR) factorization of the KKT matrix. The classical CR method has good observed performance, but its numerical stability properties need further study for our KKT system. Finally, we discuss modifications to the CR decomposition that improve performance, and we apply the approach to four industrially relevant case studies. On the largest problem, a parallel speedup of a factor of four is observed when using eight processors. [ABSTRACT FROM AUTHOR]

Dynamic optimization problems are constrained by differential and algebraic equations and are found everywhere in science and engineering. A well-established method to solve these types of problems is direct transcription, where the differential equations are replaced with discretized approximations based on finite-difference or Runge-Kutta schemes. However, for problems with thousands of state variables and discretization points, direct transcription may result in nonlinear optimization problems which are too large for general-purpose optimization solvers to handle. Also, when an interior-point solver is applied, the dominant computational cost is solving the linear systems resulting from the Newton step. For large-scale nonlinear programming problems, these linear systems may become prohibitively expensive to solve. Furthermore, the systems also become too large to formulate and store in memory of a standard computer. On the other hand, direct transcription can exploit sparsity and structure of the linear systems in order to overcome these challenges. In this paper we investigate and compare two parallel linear decomposition algorithms, Cyclic Reduction (CR) and Schur complement decomposition, which take advantage of structure and sparsity. We describe the numerical conditioning of the CR algorithm when applied to the linear systems arising from dynamic optimization problems, and then compare CR with Schur complement decomposition on a number of test problems. Finally, we propose conditions under which each should be used, and describe future research directions. [ABSTRACT FROM AUTHOR]

We present Accelerated Cyclic Reduction (ACR), a distributed-memory fast solver for rank-compressible block tridiagonal linear systems arising from the discretization of elliptic operators, developed here for three dimensions. Algorithmic synergies between Cyclic Reduction and hierarchical matrix arithmetic operations result in a solver that has O ( k N log N ( log N + k 2 ) ) arithmetic complexity and O ( k   N log  N ) memory footprint, where N is the number of degrees of freedom and k is the rank of a block in the hierarchical approximation, and which exhibits substantial concurrency. We provide a baseline for performance and applicability by comparing with the multifrontal method with and without hierarchical semi-separable matrices, with algebraic multigrid and with the classic cyclic reduction method. Over a set of large-scale elliptic systems with features of nonsymmetry and indefiniteness, the robustness of the direct solvers extends beyond that of the multigrid solver, and relative to the multifrontal approach ACR has lower or comparable execution time and size of the factors, with substantially lower numerical ranks. ACR exhibits good strong and weak scaling in a distributed context and, as with any direct solver, is advantageous for problems that require the solution of multiple right-hand sides. Numerical experiments show that the rank k patterns are of O (1) for the Poisson equation and of O ( n ) for the indefinite Helmholtz equation. The solver is ideal in situations where low-accuracy solutions are sufficient, or otherwise as a preconditioner within an iterative method. [ABSTRACT FROM AUTHOR]

Extensions have been developed, of several variants of the stride of two cyclic reduction method. The extensions refer to quasi-tridiagonal linear equation systems involving two additional nonzero elements in the first and last rows of the equation matrix, adjacent to the main three diagonals. Equations of this kind arise, for example, in the simulations of biosensors or other electrochemical systems by solving relevant ordinary or partial differential equations by finite difference methods, when boundary derivatives are approximated by one-sided, multipoint finite differences. The correctness of the algorithms developed has been verified using example matrices with pseudo-random coefficients, under conditions of both sequential and parallel execution. [ABSTRACT FROM AUTHOR]

We provide effective algorithms for solving block tridiagonal block Toeplitz systems with m × m quasiseparable blocks, as well as quadratic matrix equations with m × m quasiseparable coefficients, based on cyclic reduction and on the technology of rank-structured matrices. The algorithms rely on the exponential decay of the singular values of the off-diagonal submatrices generated by cyclic reduction. We provide a formal proof of this decay in the Markovian framework. The results of the numerical experiments that we report confirm a significant speed up over the general algorithms, already starting with the moderately small size m ≈ 10 2 . [ABSTRACT FROM AUTHOR]

It was recently observed in [10] that the singular values of the off-diagonal blocks of the matrix sequences generated by the Cyclic Reduction algorithm decay exponentially. This property was used to solve, with a higher efficiency, certain quadratic matrix equations encountered in the analysis of queuing models. In this paper, we provide a theoretical bound to the basis of this exponential decay together with a tool for its estimation based on a rational interpolation problem. Numerical experiments show that the bound is often accurate in practice. Applications to solving n × n block tridiagonal block Toeplitz systems with n × n quasiseparable blocks and certain generalized Sylvester equations in O ( n 2 log ⁡ n ) arithmetic operations are shown. [ABSTRACT FROM AUTHOR]

The geometric mean of two matrices is considered from a computational viewpoint. Several numerical algorithms based on different properties and representations of the geometric mean are discussed and analyzed. It is shown that most of the algorithms can be classified in terms of the rational approximations of the inverse square root function. A review of relevant applications is given. Copyright © 2015 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]