Search

In this paper, an efficient lopsided double-step (LDS) iteration scheme is proposed to quickly solve complex symmetric linear systems, by using the real part and imaginary part of the coefficient matrix. We give detailed analysis of the spectral radius of the iteration matrix and the quasi-optimal parameter for the LDS method. In addition, a modified version of the LDS (MLDS) method is developed by using only one matrix inversion in each iteration, and the convergence properties of the MLDS method are discussed. Particularly, under suitable conditions, the convergence factors of the LDS and the MLDS methods are no more than 0.1768, and this number is less than that of many exiting methods. Numerical experiments are implemented and the results support the contention that the LDS and the MLDS methods are more efficient than several classical methods. Furthermore, we also explore the fixed parameters for the LDS and the MLDS methods in practice, and the numerical results are very satisfactory. [ABSTRACT FROM AUTHOR]

The parameterized block splitting (PBS) is a convergent and efficient iterative method to solve the large complex symmetric linear systems. In this paper, by using PBS iterative technique, the Newton equation is approximately solved, then we establish the modified Newton-PBS iterative method to solve the complex nonlinear systems whose Jacobian matrices are large, sparse, and complex symmetric. Subsequently, the local convergence analysis are explored under appropriate conditions. Ultimately, we apply the new method and several known methods to experimental numerical examples, and experimental results verify the superiority and efficiency of our new method. Especially, in terms of CPU time and iteration steps, our method is obviously better. [ABSTRACT FROM AUTHOR]

In this paper, for solving the vertical linear complementarity problem (VLCP) effectively, a two-step new modulus-based matrix splitting (TNMMS) iteration method is introduced. Its convergence properties are discussed in depth. The efficiency of the proposed method is confirmed by some numerical experiments from the 2-D boundary problem. Numerical results show that the proposed method is superior to some existing methods, such as the two modulus-based matrix splitting (TMMS) iteration method (Numer. Algor., 2011, 57: 83–99) and the new modulus-based matrix splitting (NMMS) iteration method (Optim., 2023, 72: 2499–2516). [ABSTRACT FROM AUTHOR]

The dangling nodes are the nodes with no out-links in the web graph. It saves many computational costs if the dangling nodes are lumped into one node. In this paper, motivated by so many dangling nodes in web graphs, we mainly develop theoretical results for the modified hyperlink-induced topic search (MHITS) model by the lumping method, and the results are also suitable for the HITS model. There are three main findings in the theoretical analysis. First, MHITS can be lumped, although the matrix involved is not stochastic. Second, the hub vector of the nondangling nodes can be computed separately from dangling nodes, and the hub vector of the dangling nodes is parallel to a vector of all ones in MHITS. Third, the authority vector of the nondangling nodes is difficult to compute separately from dangling nodes. The numerical results not only show the feasibility and effectiveness of theoretical analyses, but also demonstrate that the lumped MHITS method can produce a better initial authority vector after the iteration of computing the hub vector. [ABSTRACT FROM AUTHOR]

In this paper, to solve the three-by-three block saddle-point problem, a new block triangular (NBT) preconditioner is established, which can effectively avoid the solving difficulty that the coefficient matrices of linear subsystems are Schur complement matrices when the block preconditioner is applied to the Krylov subspace method. Theoretical analysis shows that the iteration method produced by the NBT preconditioner is unconditionally convergent. Besides, some spectral properties are also discussed. Finally, numerical experiments are provided to show the effectiveness of the NBT preconditioner. [ABSTRACT FROM AUTHOR]

This paper is devoted to the accuracy and stability of quaternion Gaussian elimination (qGE). First, considering the noncommutativity of quaternion multiplications, we establish the rules of quaternion floating-point operations. After that, roundoff error analyses of quaternion LU and qGE with partial pivoting (qGEPP) are presented to show the backward stability of qGEPP is affected by the growth factor. Then, the upper bounds for growth factors of qGE with partial or complete pivoting, and the quaternion matrices with maximal growth factor are investigated. Finally, growth factors of some special matrices are also studied, and the theoretical results are confirmed through several numerical experiments. A conjecture about the growth factor of quaternion Hadamard matrix is given. [ABSTRACT FROM AUTHOR]

In this paper, by transforming the vertical linear complementarity problem (VLCP) as a certain absolute value equation, we design a class of modulus-based matrix splitting iteration methods for solving the VLCP. The convergence properties of the proposed methods are discussed in depth. By making use of some numerical experiments, we confirm the efficiency of the proposed methods. Numerical results show that the proposed methods are superior to the classical modulus-based matrix splitting iteration methods. [ABSTRACT FROM AUTHOR]

In this paper, an algorithm is proposed to compute the inverse of an invertible matrix. The new algorithm is a generalization of the algorithms based on the well-known Schultz-type iterative methods. We show that the convergence order of the new method is a linear combination of the Fibonacci sequence and also is powerful and efficient in finding and keeping sparsity of the obtained approximate inverse of sparse matrices. The convergence of the algorithm is analysed and some applications are studied. It is shown that the proposed algorithm can be used for computing an approximation of the Moore–Penrose inverse of matrices. Numerical examples are provided to verify the feasibility and effectiveness of the new method. [ABSTRACT FROM AUTHOR]

In this paper, first we present an elementary approach for evaluating the determinant of an n-by-n periodic tridiagonal matrix with Toeplitz structure, which is based on the use of a certain type of matrix reformulation and linear transformation. Then, we propose a more efficient numerical algorithm with the cost of 12 ⌊ n - 4 k ⌋ + 12 k + O (log n) for computing n-th order periodic tridiagonal Toeplitz determinants, where k is an integer that needs to be chosen at the beginning of the algorithm. Moreover, for periodic tridiagonal Toeplitz matrices with rational entries, we derive a fast and reliable algorithm to determine nonzero determinants via modular arithmetic. Some illustrative examples are provided, and the numerical results are compared with the ones obtained by Gaussian elimination algorithm and MATLAB built-in function. [ABSTRACT FROM AUTHOR]

As a specific kind of banded matrices, heptadiagonal matrices arise frequently in a variety of fields in theoretical and computational chemistry. In this paper, we present a fast and reliable algorithm for numerically evaluating the determinants of heptadiagonal Toeplitz matrices by a certain type of matrix reordering and partitioning, and linear transformation. In this algorithm, we show that the determinant of an n-by-n heptadiagonal Toeplitz matrix can be implicitly evaluated by computing the determinant of a 6-by-6 matrix which is obtained after the (n−6)th iteration of linear transformation of a 6-by-3 matrix. The results of some numerical experiments are provided to illustrate the accuracy and efficiency of the proposed algorithm and its competitiveness with Gaussian elimination algorithm and MATLAB built-in function. [ABSTRACT FROM AUTHOR]

As a generalization of k-tridiagonal matrices, many variations of (p,q)-tridiagonal matrices have attracted much attention over the years. In this paper, we present an efficient algorithm for numerically computing the inverses of n-square (p,q)-tridiagonal matrices under a certain condition. The algorithm is based on the combination of a bidiagonalization approach which preserves the banded structure and sparsity of the original matrix, and a recursive algorithm for inverting general lower bidiagonal matrices. Some numerical results with simulations in MATLAB implementation are provided in order to illustrate the accuracy and efficiency of the proposed algorithms, and its competitiveness with MATLAB built-in function. [ABSTRACT FROM AUTHOR]

In this paper, first we propose a general modulus-based matrix splitting iteration method for solving horizontal linear complementarity problems. In order to improve the computing efficiency, we further propose a preconditioned general modulus-based matrix splitting iteration method. We establish the convergence theorems when the coefficient matrices are (symmetric) positive definite matrices and H+-matrices, respectively. Numerical results show that the proposed preconditioned general modulus-based matrix splitting iteration method is superior than some existing methods and the general modulus-based matrix splitting iteration method. [ABSTRACT FROM AUTHOR]

The block version of GMRES (BGMRES) is most advantageous over the single right hand side (RHS) counterpart when the cost of communication is high while the cost of floating point operations is not. This is the particular case on modern graphics processing units (GPUs), while it is generally not the case on traditional central processing units (CPUs). In this paper, experiments on both GPUs and CPUs are shown that compare the performance of BGMRES against GMRES as the number of RHS increases, with a particular forcus on GPU performance. The experiments indicate that there are many cases in which BGMRES is slower than GMRES on CPUs, but faster on GPUs. Furthermore, when varying the number of RHS on the GPU, there is an optimal number of RHS where BGMRES is clearly most advantageous over GMRES. A computational model for the GPU is developed using hardware specific parameters, providing insight towards how the qualitative behavior of BGMRES changes as the number of RHS increase, and this model also helps explain the phenomena observed in the experiments. [ABSTRACT FROM AUTHOR]

Seriation is a problem consisting of seeking the best enumeration order of a set of units whose interrelationship is described by a bipartite graph. An algorithm for spectral seriation based on the use of the Fiedler vector of the Laplacian matrix associated to the problem was developed by Atkins et al. under the assumption that the Fiedler value is simple. In this paper, we analyze the case in which the Fiedler value of the Laplacian is not simple, discuss its effect on the set of the admissible solutions, and study possible approaches to actually perform the computation. Examples and numerical experiments illustrate the effectiveness of the proposed methods. [ABSTRACT FROM AUTHOR]

The Hermitian and skew-Hermitian splitting (HSS) method is a well-known method employed in solving the non-Hermitian positive definite linear systems. However, the performance of the HSS method highly depends on the parameter value. In this paper, we address this issue by introducing two practical selections of this parameter, which are computed based on the Rayleigh quotient of the Hermitian part of the coefficient matrix. On the basis of the new selections, we propose the variable-parameter HSS methods for non-Hermitian positive definite linear systems and provide a convergent analysis under reasonable assumptions. Furthermore, to verify the effectiveness of our selections, we conduct experiments on several large and sparse linear systems. The numerical results show their efficiency over the existing quasi-optimal parameter. [ABSTRACT FROM AUTHOR]

In this paper, we consider iterative solution of certain large scale block two-by-two linear systems arising from numerical solution process of some PDE-constrained optimal control problems. Based upon skillful rotating technique, a new fast and robust stationary iteration method is constructed from the idea of classical block successive over relaxation (BSOR) iteration. Equipped with a practical problem independent parameter choice strategy, the proposed method can result in a sharp parameter independent convergence rate close to 0.17. Moreover, a robust preconditioner is developed from an equivalent form of the new iteration method, which is suitable for inexact variable right preconditioning within Krylov subspace acceleration. Numerical examples from both distributed steady control problem and unsteady control problem which leads to complex Kronecker structured linear system are tested to show that the new solution methods are competitive to some existing ones. [ABSTRACT FROM AUTHOR]

In this paper, we present an efficient numerical algorithm for evaluating the determinants of general bordered k-tridiagonal matrices in linear time. The algorithm is based on a novel incomplete block-diagonalization (IBD) approach which preserves the low-rank structure and sparsity of the original matrix, and a reliable algorithm for the determinants of general bordered tridiagonal matrices. An advantage of the proposed algorithm is that there is no division operation involved and hence the algorithm will never suffer from breakdown. Moreover, the algorithm theoretically produces exact values of the determinants when all entries of the bordered k-tridiagonal matrix are given in integer. Some numerical results with simulations in Matlab implementation are provided in order to illustrate the accuracy and effectiveness of the proposed algorithm, and its competitiveness with Gaussian elimination algorithm and MATLAB built-in function. [ABSTRACT FROM AUTHOR]

The paper is devoted to a posteriori error identities for the stationary reaction–convection–diffusion problem with mixed Dirichlét–Neumann boundary conditions. They reflect the most general relations between deviations of approximations from the exact solutions and those values that can be observed in a numerical experiment. The identities contain no mesh dependent constants and are valid for any function in the admissible (energy) class. Therefore, the identities and the estimates that follow from them generate universal and fully reliable tools of a posteriori error control. [ABSTRACT FROM AUTHOR]

In this paper, based on the published works by Bai and Tong (J. Univ. Electr. Sci. Tech. China 22:420–424, 1993) and Bai and Huang (J. Univ. Electr. Sci. Tech. China 23:428–432, 1994), we design a class of new modulus-based matrix splitting methods for solving the implicit complementarity problem (ICP) by a new equivalent fixed-point form of the ICP. Some sufficient conditions to guarantee the convergence of the proposed method are presented. Numerical examples are offered to show the efficiency of the proposed method. [ABSTRACT FROM AUTHOR]

In this paper, we discuss the modulus-based matrix splitting iteration method for solving a class of nonlinear complementarity problems under a weakened condition, and present the general convergence conditions for the method in terms of spectral radius and matrix norm, respectively. Moreover, for some special cases of the method, we propose the concrete convergence conditions and optimal parameters. These convergence theories improve the existing results to some extent. The numerical experiments verify the validity and practicality of the presented results. [ABSTRACT FROM AUTHOR]

Recently, a number of efficient iteration methods for the solution of a special class of block 3 × 3 saddle point systems have been proposed by some authors. In order to easily evaluate the strong stability of these numerical algorithms and provide a practical and reliable termination criterion, in this paper, we perform the structured backward error analysis for this type of block 3 × 3 saddle point system and present an explicit and computable formula of the normwise structured backward error. Some numerical experiments are performed to demonstrate that our results can be used to easily test the stability of running algorithms, and the new stopping criterion based on the derived structured backward error is more suitable and efficient than the commonly used residue-based one. [ABSTRACT FROM AUTHOR]

In the present paper, we consider the solution of periodic tridiagonal Toeplitz linear systems. By exploiting the special low-rank and Toeplitz structure, we give a new structure-preserving decomposition form of the coefficient matrix. Based on this matrix decomposition form and combined with elementary column operations, we give different algorithms for the fast and reliable solutions of three types of periodic tridiagonal Toeplitz linear systems. Compared with the LU\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\varvec{LU}$$\end{document} decomposition method, our proposed algorithms take less computational costs and need less memory storage and data transmission. Numerical experiments are given to demonstrate the accuracy and efficiency of our algorithms. All of the experiments are performed on a computer with the aid of programs written in MATLAB. [ABSTRACT FROM AUTHOR]

Recently, Chen and Ma [A generalized shift-splitting preconditioner for complex symmetric linear systems, J. Comput. Appl. Math., 344 (2018), pp. 691–700] have presented the generalized shift-splitting (GSS) method to solve complex symmetric linear systems. In this paper, we establish a class of modified GSS (MGSS) method to extend the existing GSS method. We prove the convergence of the proposed method under suitable restrictions on the iteration parameters. Lastly, numerical experiments are carried out, and experimental results show that the new iteration method is feasible and effective. [ABSTRACT FROM AUTHOR]

(p,q)-Pentadiagonal matrices have received considerable attention in recent years, which are a generalization of pentadiagonal matrices. In this paper, a breakdown-free algorithm is presented for numerically evaluating the determinants of n-by-n (p,q)-pentadiagonal matrices. The algorithm is based on the use of a reliable tridiagonalization process which preserves the banded structure and sparsity of the original matrix. Numerical examples are given in order to illustrate the effectiveness of the proposed algorithm. All of the experiments are performed on a computer with the aid of programs written in MATLAB. [ABSTRACT FROM AUTHOR]

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]

In this paper, efficient algorithms will be studied for solving nonlinear saddle point problems from the elliptic optimal control problems. Based on the preconditioned inexact Uzawa (PIU) algorithmic framework, an improved preconditioned inexact Uzawa (I-PIU) algorithmic framework will first be constructed for solving a class of block-structured nonlinear systems, which possess a more general form of the nonlinear saddle point systems. When the I-PIU algorithmic framework is used for solving the block-structured nonlinear systems, a detailed theoretical analysis of the global convergence properties is proposed under the case that the nonlinear operator is single-valued. Besides, a special I-PIU method is established based on a new matrix splitting technique at the first iterative step of the I-PIU algorithmic framework, and then we establish the detailed theoretical results of the convergence. Finally, some numerical experiments are given to demonstrate the efficiency of the I-PIU method. [ABSTRACT FROM AUTHOR]