Search

This paper introduces a class of new extended generalized shift-splitting (NEGSS) preconditioners for solving the 3 × 3 block saddle point problems (SPPs). The algorithm implementation of the NEGSS preconditioner, the convergence of the NEGSS iteration method and the eigenvalue distribution of the corresponding preconditioned matrix with parameter t are investigated. Numerical experiments demonstrate the effectiveness of the proposed method and verify our theoretical results. [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]

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, inspired by the simplified relaxed alternating positive semi-definite splitting preconditioner (Xiong and Li in J Appl Math Comput, 2023), a modified preconditioner is established to solve the three-by-three block saddle point problems. The advantage of the modified preconditioner is that its parameters can be easy to select, which can avoid the work of the calculation of the parameters. Next, the spectral property of the preconditioned matrix with modified preconditioner is also discussed. In the end, three examples are provided to show the effectiveness of the modified preconditioner. [ABSTRACT FROM AUTHOR]

In this paper, a new matrix splitting (NS) is given based on the coefficient matrix of the double saddle point problems, and a modified new matrix splitting (MNS) preconditioner is also proposed. Theoretical analysis proves that the iteration method produced by the MNS preconditioner is convergent with any positive parameters under assumed conditions and the eigenvalues of the MNS preconditioned matrix are located in a positive interval. Numerical examples verify the efficiency of the proposed preconditioner. [ABSTRACT FROM AUTHOR]

As a generalization of the tridiagonal matrices, k-tridiagonal matrices have been attracted much attention in the last few years. In this paper, we present an explicit expression for the arbitrary positive integer powers of k-tridiagonal matrices with Toeplitz structure. Two numerical examples are given to demonstrate the validity of the proposed results. [ABSTRACT FROM AUTHOR]

In multivariate regression analysis, a coefficient matrix is used to relate multiple response variables to regressor variables in a noisy linear system from given data. Optimization is a natural approach to find such coefficient matrix with few nonzero rows. However, the relationship of most group sparse optimization models with cardinality penalty or cardinality constraints is not clear. In this paper, we give a comprehensive description of the relationship between three widely used group sparse optimization problems with cardinality terms: (i) the number of nonzero rows is minimized subject to an error tolerance for regression; (ii) the error for regression is minimized subject to a row cardinality constraint; (iii) the sum of the number of nonzero rows and error for regression is minimized. The first two problems have convex constraints and cardinality constraints respectively, while the third one is an unconstrained optimization problem with a cardinality penalty. We provide sufficient conditions under which the three optimization problems have the same global minimizers. Moreover, we analyze the relationship of stationary points and local minimizers of the three problems. Finally, we use two examples to illustrate our theoretical results for finding solutions of constrained optimization problems involving cardinality terms by unconstrained optimization problems with penalty functions. [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,we devote to improve an effective iterative method for solving weakly nonlinear systems with large sparse complex symmetric Jacobian matrix. Employing the Anderson mixing to speed up the convergence of double-step scale splitting (DSS) iteration, we establish a modified DSS (MDSS) iteration method for solving linear system with complex symmetric matrix. We propose the Picard-MDSS method based on the separability of linear and nonlinear terms by combining modified DSS (MDSS) methods of linear systems. We explore convergence theorems for the MDSS and Picard-MDSS methods under proper conditions. Furthermore, we conclude that our new methods are more efficient in comparison to several known methods through numerical experiments. The numerical results show the superiority of our new methods in CPU time and iteration steps. [ABSTRACT FROM AUTHOR]

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 article studies quantitative relations (error identities) that characterize distances between exact solutions of nonlinear evolutionary problems and functions considered as approximations. The restrictions imposed on such a function are minimal and actually come down to the condition that it belongs to the same functional class as the generalized solution of the problem under consideration. Functional identities of this type reflect the most general relations between deviations from exact solutions of parabolic initial boundary value problems and those data 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 regardless of the method by which it was constructed. Therefore, they can serve as basic tools for deriving fully reliable a posteriori estimates of approximation errors as well as for analysis of modeling errors. The corresponding examples are discussed in the paper. [ABSTRACT FROM AUTHOR]

In the present paper, we mainly consider the direct solution of periodic pentadiagonal Toeplitz linear systems. By exploiting the low-rank and Toeplitz structure of the coefficient matrix, we derive a new matrix decomposition of periodic pentadiagonal Toeplitz matrices. Based on this matrix decomposition form and combined with the Sherman-Morrison-Woodbury formula, we propose an efficient algorithm for numerically solving periodic pentadiagonal Toeplitz linear systems. Furthermore, we present a fast and reliable algorithm for evaluating the determinants of periodic pentadiagonal Toeplitz matrices by a certain type of matrix reordering and partitioning, and linear transformation. Numerical examples are given to demonstrate the performance and effectiveness of our algorithms. All of the experiments are performed on a computer with the aid of programs written in Matlab. [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]

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]

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]

Based on the ideas of the projected matrix splitting technique and the well-known successive overrelaxation (SOR) iteration method, a projected SOR (PSOR) iteration method is studied in this paper for solving a class of vertical linear complementarity problems, where the system matrix is a vertical block matrix of several square sub-blocks with positive diagonal elements. Convergence analyses of the PSOR iteration method are carefully studied when the square sub-blocks and their row-representative matrices are strictly diagonally dominant, irreducibly diagonally dominant and H + -matrices, respectively. At last, two numerical examples are presented. Numerical results indicate that the PSOR method performs much better than some recent proposed projected splitting methods. [ABSTRACT FROM AUTHOR]

In this paper, I present an efficient reordering-based preconditioner for the elliptic PDE-constrained optimization problems. The proposed preconditioner is extracted from a stationary iterative method which is convergent under certain suitable conditions. In addition, the spectral properties of the corresponding preconditioned matrix are studied. The resulting preconditioner is efficient for solving problems with small Tikhonov parameters (less than 1 e - 6 ). Numerical experiments are presented to illustrate the effectiveness of the proposed preconditioner. [ABSTRACT FROM AUTHOR]

Matrix inverse computation is one of the fundamental mathematical problems of numerical linear algebra and has been widely used in various fields of computer science and engineering. In the current paper, a reliable and efficient algorithm is presented for numerically computing the inverses of n-square ( p , q )-pentadiagonal matrices. The algorithm is based on the combination of a tridiagonalization approach which preserves the banded structure and sparsity of the original matrix, and a recursive algorithm for inverting general tridiagonal matrices. The experimental results of some representative numerical examples are provided to demonstrate the performance and effectiveness of the proposed algorithm 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]

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]

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 this paper, we present a parameterized inexact Uzawa type method for solving a class of large sparse generalized saddle point problems, and analyze its convergence using a different approach from those utilized in the existing literature. Some numerical results are given to illustrate the effectiveness of the proposed method. [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]

This paper deals with solving a class of three-by-three block saddle point problems. The systems are solved by preconditioning techniques. Based on an iterative method, we construct a block upper triangular preconditioner. The convergence of the presented method is studied in details. Finally, some numerical experiments are given to demonstrate the superiority of the proposed preconditioner over some existing ones. [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]

In this paper, we discuss a modulus-based matrix splitting iteration method for solving the implicit complementarity problems and propose the convergence conditions from the spectral radius and matrix norm. The numerical experiments show the practicality of the method and the validity of the convergence conclusions. [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]

In this paper, we are mainly concerned with the iterative method for solving the block-Toeplitz linear system. Based on the exact block Schur complement factorization of the block-Toeplitz coefficient matrix, a class of parameterized robust Schur complement preconditioner is constructed, which relies on Sherman-Morrison-Woodbury inversion formula of the Schur complement of the partitioned coefficient matrix. Meanwhile, we show that the new preconditioned system can result in much better spectrum distributions than some existing preconditioners, and deflate some small eigenvalues of the preconditioned matrix. The convergence analysis of our proposed method is established, and a strategy for the practical choice of an optimal parameter is given. Numerical experiments arising from image restoration are provided, which show the proposed preconditioner is effective and confirm our theoretical results are correct. [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]

Seriation is an important ordering problem which consists of finding the best ordering of a set of units whose interrelationship is defined by a bipartite graph. It has important applications in, e.g., archaeology, anthropology, psychology, and biology. This paper presents a Matlab implementation of an algorithm for spectral seriation by Atkins et al., based on the use of the Fiedler vector of the Laplacian matrix associated to the problem, which encodes the set of admissible solutions into a PQ-tree. We introduce some numerical technicalities in the original algorithm to improve its performance, and point out that the presence of a multiple Fiedler value may have a substantial influence on the computation of an approximated solution, in the presence of inconsistent data sets. Practical examples and numerical experiments show how to use the toolbox to process data sets deriving from real-world applications. [ABSTRACT FROM AUTHOR]

In this paper, we propose the meshless finite point method for solving a type of fluid flow problem. The moving least square function is combined with the collocation method to treat nonlinear one- and two-dimensional soil water-salt movement equations. An adaptive windward scheme is used to stabilize the numerical solution in regions with a large gradient change. Numerical examples with the comparison among the proposed method, finite element method and characteristic finite element method show that the meshless finite point method is more accurate and is used to eliminate the numerical oscillation phenomenon. [ABSTRACT FROM AUTHOR]