Randomized Kaczmarz solver for noisy linear systems

The Kaczmarz method is an iterative algorithm for solving systems of linear equations Ax=b. Theoretical convergence rates for this algorithm were largely unknown until recently when work was done on a randomized version of the algorithm. It was proved that for overdetermined systems, the randomized Kaczmarz method converges with expected exponential rate, independent of the number of equations in the system. Here we analyze the case where the system Ax=b is corrupted by noise, so we consider the system Ax≈b+r where r is an arbitrary error vector. We prove that in this noisy version, the randomized method reaches an error threshold dependent on the matrix A with the same rate as in the error-free case. We provide examples showing our results are sharp in the general context.     

A fast solver for riemann problems

An efficient algorithm is presented for solving the Riemann problem for a polytropic gas. It enables the user to compute the solution for all physically reasonable data. The convergence of the algorithm is proved. The accuracy of the solution is limited only by the accuracy of the computer. There is an a-priori estimation of the required number of iterations. The rate of convergence turns out to be much higher than that of the usual fixed point iteration scheme.     

An asynchronous direct solver for banded linear systems

Banded linear systems occur frequently in mathematics and physics. However, direct solvers for large systems cannot be performed in parallel without communication. The aim of this paper is to develop a general asymmetric banded solver with a direct approach that scales across many processors efficiently. The key mechanism behind this is that reduction to a row-echelon form is not required by the solver. The method requires more floating point calculations than a standard solver such as LU decomposition, but by leveraging multiple processors the overall solution time is reduced. We present a solver using a superposition approach that decomposes the original linear system into q subsystems, where q is the number of superdiagonals. These methods show optimal computational cost when q processors are available because each system can be solved in parallel asynchronously. This is followed by a q×q dense constraint matrix problem that is solved before a final vectorized superposition is performed. Reduction to row echelon form is not required by the solver, and hence the method avoids fill-in. The algorithm is first developed for tridiagonal systems followed by an extension to arbitrary banded systems. Accuracy and performance is compared with existing solvers and software is provided in the supplementary material.     

A fast Poisson solver

Summary A direct method is developed for the discrete solution of Poisson's equation on a rectangle. The algorithm proposed is of the class of marching methods. The idea is to generalize the classical Cramer's method using Chebyshev matrix polynomials formalism. This results in the solution ofN independent diagonal system of linear equations in the eigenvector coordinate system. An elementary transformation to the original coordinate system is then carried out.     

A fast solver for integral equations with convolution-type Kernel

This paper studies the data redundancy of the coefficient matrix of the corresponding discrete system which forms a basis for fast algorithms of solving the integral equation whose kernel includes a convolution function factor. We develop lossless matrix compression strategies, which reduce the cost of integral evaluations and the storage to linear complexity, i.e., the same order of the approximation space dimensions. We establish that this algorithm preserves the convergence order of the approximate solution. We also propose a hardware-aware parallel algorithm for these strategies.     

A fast multiscale solver for modified Hammerstein equations

This paper presents a fast solver, called the multilevel augmentation method, for modified nonlinear Hammerstein equations. When we utilize the method to solve a large scale problem, most of components of the solution can be computed directly, and lower frequency components can be obtained by solving a fixed low-order algebraic nonlinear system. The advantage of using the algorithm to modified equations is that it leads to reduce the cost of numerical integrations greatly. The optimal error estimate of the method is established and the nearly linear computational complexity is proved. Finally, numerical examples are presented to confirm the theoretical results and illustrate the efficiency of the method.     

A fast Poisson solver on disks

We present a fast/parallel Poisson solver on disks, based on efficient evaluation of the exact solution given by the Newtonian potential and the Poisson integral. Derived from an integral formulation, it is more accurate and simpler in parallel implementation and in upgrading to a higher order algorithm, than an algorithm which solves the linear system obtained from a differential formulation.     

A fast direct solver for elliptic problems with a divergence constraint

A fast direct solution method for a discretized vector‐valued elliptic partial differential equation with a divergence constraint is considered. Such problems are typical in many disciplines such as fluid dynamics, elasticity and electromagnetics. The method requires the problem to be posed in a rectangle and boundary conditions to be either periodic boundary conditions or the so‐called slip boundary conditions in one co‐ordinate direction. The arising saddle‐point matrix has a separable form when bilinear finite elements are used in the discretization. Based on a result for so‐called p‐circulant matrices, the saddle‐point matrix can be transformed into a block‐diagonal form by fast Fourier transformations. Thus, the fast direct solver has the same structure as methods for scalar‐valued problems which are based on Fourier analysis and, therefore, it has the same computational cost ??(N log N). Numerical experiments demonstrate the good efficiency and accuracy of the proposed method. Copyright © 2002 John Wiley & Sons, Ltd.     

Iterative solver for systems of linear equations with a sparse stiffness matrix on clusters

In this paper, a package of programs for solving systems of linear equations with a sparse matrix for computers with distributed memory is proposed. The package is based on an iterative algorithm for solving the initial system of equations with a preconditioner constructed using an algebraic domain decomposition. Such an approach makes it possible to simultaneously multiply the preconditioner and the stiffness matrix by a vector on a cluster. Also, to improve the efficiency of computation, the functionalities PARDISO and Sparse BLAS of the Intel®MKL library are used on each process. In addition to processes parallelization, the package uses OpenMP parallelization on each of these processes, as well as Intel®MKL internal functional parallelization.     

A normalized sparse linear equations solver

Normalized factorization procedures for the solution of large sparse linear finite element systems have been recently introduced in [3]. In these procedures the large sparse symmetric coefficient matrix of irregular structure is factorized exactly to yield a normalized direct solution method. Additionally, approximate factorization procedures yield implicit iterative methods for the finite difference or finite element solution. The numerical implementation of these algorithms is presented here and FORTRAN subroutines for the efficient solution of the resulting large sparse symmetric linear systems of algebraic equations are given.     

A fast algorithm for solving systems of linear equations with two variables per equation

We present a fast algorithm for solving m X n systems of linear equations Ax = c with at most two variables per equation. The algorithm makes use of a linear-time algorithm for constructing a spanning forest of an undirected graph, and it requires 5m + 2n – 2 arithmetic operations in the worst case.     

The fast quartic solver

A fast and highly accurate algorithm for solving quartic equations is introduced. This new algorithm is more than six times as fast and several times more accurate than the quasi-standard Companion matrix eigenvalue quartic solver. Moreover, the method is exceptionally robust in cases of extreme root spread. The new algorithm is based on a factorization of the quartic in two quadratics, which are solved in closed form. The performance key at this point is a fixed-point iteration based fitting algorithm for backward optimization of the underlying quartic-to-quadratic polynomial decomposition. Detailed experimental results confirm our claims.     

ARMS: an algebraic recursive multilevel solver for general sparse linear systems

This paper presents a general preconditioning method based on a multilevel partial elimination approach. The basic step in constructing the preconditioner is to separate the initial points into two parts. The first part consists of ‘block’ independent sets, or ‘aggregates’. Unknowns of two different aggregates have no coupling between them, but those in the same aggregate may be coupled. The nodes not in the first part constitute what might be called the ‘coarse’ set. It is natural to call the nodes in the first part ‘fine’ nodes. The idea of the methods is to form the Schur complement related to the coarse set. This leads to a natural block LU factorization which can be used as a preconditioner for the system. This system is then solved recursively using as preconditioner the factorization that could be obtained from the next level. Iterations between levels are allowed. One interesting aspect of the method is that it provides a common framework for many other techniques. Numerical experiments are reported which indicate that the method can be fairly robust. Copyright © 2002 John Wiley & Sons, Ltd.     

A fast solver for the first biharmonic boundary value problem

Summary This paper provides a fast and storage-saving method for the solution of the first biharmonic boundary value problem (b.v.p.). The b.v.p. is approximated via a special variational finite difference technique suggested earlier by V.G. Korneev. It is shown theoretically that our method produces an approximate solution to the finite difference equations inO(NlnNln^–1) arithmetical operations, whereN is the number of unknowns and (0<<1) denotes the relative accuracy required. The numerical results obtained by our computer code CGMFC decisively substantiate the theoretical estimates given.     

A fast convergent iterative solver for approximate inverse of matrices

In this paper, a rapid iterative algorithm is proposed to find robust approximations for the inverse of nonsingular matrices. The analysis of convergence reveals that this high‐order method possesses eighth‐order convergence. The interesting point is that, this rate is attained using less number of matrix‐by‐matrix multiplications in contrast to the existing methods of the same type in the literature. The extension of the method for finding Moore–Penrose inverse of singular or rectangular matrices is also presented. Numerical comparisons will be given to show the applicability, stability and consistency of the new scheme by paying special attention on the computational time. Copyright © 2013 John Wiley & Sons, Ltd.     

A domain-decomposing parallel sparse linear system solver

The solution of large sparse linear systems is often the most time-consuming part of many science and engineering applications. Computational fluid dynamics, circuit simulation, power network analysis, and material science are just a few examples of the application areas in which large sparse linear systems need to be solved effectively. In this paper, we introduce a new parallel hybrid sparse linear system solver for distributed memory architectures that contains both direct and iterative components. We show that by using our solver one can alleviate the drawbacks of direct and iterative solvers, achieving better scalability than with direct solvers and more robustness than with classical preconditioned iterative solvers. Comparisons to well-known direct and iterative solvers on a parallel architecture are provided.     

Stability and performance analysis of a block elimination solver for bordered linear systems

A new block elimination method for bordered systems is proposedand its numerical properties are analysed. In the case wherethe leading principal block is ill-conditioned or singular andthe method becomes unstable a perturbation approach is usedto enhance the stability. Results of experiments performed onthe SGI Power Challenge 8000 and on the Cray J-9x illustratethe performance of the new algorithm and compare it with thecurrent best approach. It is shown that the new method worksfaster while preserving stability.     

A domain-decomposing parallel sparse linear system solver

The solution of large sparse linear systems is often the most time-consuming part of many science and engineering applications. Computational fluid dynamics, circuit simulation, power network analysis, and material science are just a few examples of the application areas in which large sparse linear systems need to be solved effectively. In this paper, we introduce a new parallel hybrid sparse linear system solver for distributed memory architectures that contains both direct and iterative components. We show that by using our solver one can alleviate the drawbacks of direct and iterative solvers, achieving better scalability than with direct solvers and more robustness than with classical preconditioned iterative solvers. Comparisons to well-known direct and iterative solvers on a parallel architecture are provided.     

A fast algorithm for subspace state-space system identification via exploitation of the displacement structure

Two recent approaches (Van Overschee, De Moor, N4SID, Automatica 30 (1) (1994) 75; Verhaegen, Int. J. Control 58(3) (1993) 555) in subspace identification problems require the computation of the R factor of the QR factorization of a block-Hankel matrix H, which, in general has a huge number of rows. Since the data are perturbed by noise, the involved matrix H is, in general, full rank. It is well known that, from a theoretical point of view, the R factor of the QR factorization of H is equivalent to the Cholesky factor of the correlation matrix H^TH, apart from a multiplication by a sign matrix. In Sima (Proceedings Second NICONET Workshop, Paris-Versailles, December 3, 1999, p. 75), a fast Cholesky factorization of the correlation matrix, exploiting the block-Hankel structure of H, is described. In this paper we consider a fast algorithm to compute the R factor based on the generalized Schur algorithm. The proposed algorithm allows to handle the rank–deficient case.     

A fast Fourier transform based direct solver for the Helmholtz problem

This article is devoted to the efficient numerical solution of the Helmholtz equation in a two‐ or three‐dimensional (2D or 3D) rectangular domain with an absorbing boundary condition (ABC). The Helmholtz problem is discretized by standard bilinear and trilinear finite elements on an orthogonal mesh yielding a separable system of linear equations. The main key to high performance is to employ the fast Fourier transform (FFT) within a fast direct solver to solve the large separable systems. The computational complexity of the proposed FFT‐based direct solver is $\mathrm{??}(N\log N)$ operations. Numerical results for both 2D and 3D problems are presented confirming the efficiency of the method discussed.