Search

This paper introduces an efficient unconditionally stable fourth-order method for solving nonlinear space-fractional reaction-diffusion systems with nonhomogeneous Dirichlet boundary conditions on bounded domains. The proposed method is based on a compact improved matrix transformed technique for fourth-order spatial approximation and exponential time differencing approximation for fourth-order time integration. The main advantage of the improved matrix transfer technique is that it leads to a system of ordinary differential equations with spatial discretization matrix raised to the desired fractional order. The key benefit of the fourth-order exponential integrator is that it can be implemented with essentially the same computational complexity as the backward Euler method by utilizing a partial fraction splitting technique in which it is just required to solve two backward Euler-type well-conditioned linear systems at each time step by computing LU decomposition of spatial discretization matrix once outside the time loop. Linear stability analysis and various numerical experiments are also performed to demonstrate stability and accuracy of the proposed method. Moreover, calculation of local truncation error and an empirical convergence analysis show the fourth-order accuracy of the proposed method.

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.

When an orthogonal matrix is partitioned into a two-by-two block structure, its four blocks can be simultaneously bidiagonalized. This observation underlies numerically stable algorithms for the CS decomposition and the existence of CMV matrices for orthogonal polynomial recurrences. We discover a new matrix decomposition for simultaneous multidiagonalization, which reduces the blocks to any desired bandwidth. Its existence is proved, and a backward stable algorithm is developed. The resulting matrix with banded blocks is parameterized by a product of Givens rotations, guaranteeing orthogonality even on a finite-precision computer. The algorithm relies heavily on Level 3 BLAS routines and supports parallel computation.

A recursive procedure for computing an approximation of the left and right dominant singular subspaces of a given matrix is proposed in [1]. The method is particularly suited for matrices with many more rows than columns. The procedure consists of a few steps. In one of these steps a Householder transformation is multiplied to an upper triangular matrix. The following step consists in recomputing an upper triangular matrix from the latter product. In [1] it is said that the latter step is accomplished in O(k(3)) operations, where k is the order of the triangular matrix. In this short note we show that this step can be accomplished in O(k(2)) operations. ispartof: Numerical Algorithms vol:38 issue:4 pages:237-242 status: published

Solving Total Least Squares (TLS) problemsAX≈B requires the computation of the noise subspace of the data matrix [A;B]. The widely used tool for doing this is the Singular Value Decomposition (SVD). However, the SVD has the drawback that it is computationally expensive. Therefore, we consider here a different so-called rank-revealing two-sided orthogonal decomposition which decomposes the matrix into a product of a unitary matrix, a triangular matrix and another unitary matrix in such a way that the effective rank of the matrix is obvious and at the same time the noise subspace is exhibited explicity. We show how this decompsition leads to an efficient and reliable TLS algorithm that can be parallelized in an efficient way.