Search

This paper presents three tensor randomized extended Kaczmarz methods for solving a tensor inconsistent linear system of equations under the t-product between tensors. The randomized extended Kaczmarz, the randomized extended block Kaczmarz, and the randomized extended greedy block Kaczmarz methods in tensor form are proposed to solve inconsistent tensor linear system of equations, respectively. The convergence of each method is proved. Several numerical examples are given to show the efficiency and effectiveness of our methods. [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]

A modular string averaging procedure (MSA, for short) for a finite number of operators was first introduced by Reich and Zalas in 2016. The MSA concept provides a flexible algorithmic framework for solving various feasibility problems such as common fixed point and convex feasibility problems. In 2001 Bauschke and Combettes introduced the notion of coherence and applied it to proving weak and strong convergence of many iterative methods. In 2019 Barshad, Reich and Zalas proposed a stronger variant of coherence which provides a more convenient sufficient convergence condition for such methods. In this paper we combine the ideas of both modular string averaging and coherence. Focusing on extending the above MSA procedure to an infinite sequence of operators with admissible controls, we establish strong coherence of its output operators. Various applications of these concepts are presented with respect to weak and strong convergence. They also provide important generalizations of known results, where the weak convergence of sequences of operators generated by the MSA procedure with intermittent controls was considered. [ABSTRACT FROM AUTHOR]

Consider the problem of solving systems of linear algebraic equations A x = b with a real symmetric positive definite matrix A using the conjugate gradient (CG) method. To stop the algorithm at the appropriate moment, it is important to monitor the quality of the approximate solution. One of the most relevant quantities for measuring the quality of the approximate solution is the A -norm of the error. This quantity cannot be easily computed; however, it can be estimated. In this paper we discuss and analyze the behavior of the Gauss-Radau upper bound on the A -norm of the error, based on viewing CG as a procedure for approximating a certain Riemann-Stieltjes integral. This upper bound depends on a prescribed underestimate μ to the smallest eigenvalue of A . We concentrate on explaining a phenomenon observed during computations showing that, in later CG iterations, the upper bound loses its accuracy, and is almost independent of μ . We construct a model problem that is used to demonstrate and study the behavior of the upper bound in dependence of μ , and developed formulas that are helpful in understanding this behavior. We show that the above-mentioned phenomenon is closely related to the convergence of the smallest Ritz value to the smallest eigenvalue of A . It occurs when the smallest Ritz value is a better approximation to the smallest eigenvalue than the prescribed underestimate μ . We also suggest an adaptive strategy for improving the accuracy of the upper bounds in the previous iterations. [ABSTRACT FROM AUTHOR]

When exploring the literature, it can be observed that the operator obtained when applying Newton-like root finding algorithms to the quadratic polynomials z2 − c has the same form regardless of which algorithm has been used. In this paper, we justify why this expression is obtained. This is done by studying the symmetries of the operators obtained after applying Newton-like algorithms to a family of degree d polynomials p(z) = zd − c. Moreover, we provide an iterative procedure to obtain the expression of new Newton-like algorithms. We also carry out a dynamical study of the given generic operator and provide general conclusions of this type of methods. [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]

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 practical computations, the (preconditioned) conjugate gradient (P)CG method is the iterative method of choice for solving systems of linear algebraic equations Ax = b with a real symmetric positive definite matrix A. During the iterations, it is important to monitor the quality of the approximate solution xk so that the process could be stopped whenever xk is accurate enough. One of the most relevant quantities for monitoring the quality of xk is the squared A-norm of the error vector x − xk. This quantity cannot be easily evaluated; however, it can be estimated. Many of the existing estimation techniques are inspired by the view of CG as a procedure for approximating a certain Riemann–Stieltjes integral. The most natural technique is based on the Gauss quadrature approximation and provides a lower bound on the quantity of interest. The bound can be cheaply evaluated using terms that have to be computed anyway in the forthcoming CG iterations. If the squared A-norm of the error vector decreases rapidly, then the lower bound represents a tight estimate. In this paper, we suggest a heuristic strategy aiming to answer the question of how many forthcoming CG iterations are needed to get an estimate with the prescribed accuracy. Numerical experiments demonstrate that the suggested strategy is efficient and robust. [ABSTRACT FROM AUTHOR]

The initial boundary value problem of the tempered fractional diffusion equations is a kind of important equations arising in many application fields. In this paper, the Crank-Nicolson scheme is applied in the discretization of the tempered fractional diffusion equations. We then get the discretized system of linear equations with the coefficient matrix having the structure of the sum of an identity matrix and the product of a diagonal and a symmetric positive-definite Toeplitz matrix. A scaled diagonal and Toeplitz-approximate splitting (SDTAS) preconditioner is developed, and the GMRES method combined with this preconditioner is applied to solve the linear system. The spectral distribution of the preconditioned matrix is analyzed and some theoretical results are given. Numerical results demonstrate that the proposed preconditioner is efficient in accelerating the convergence rate of the GMRES method. [ABSTRACT FROM AUTHOR]

The multi-step matrix splitting iteration (MPIO) for computing PageRank is an efficient iterative method by combining the multi-step power method with the inner-outer iterative method. In this paper, with the aim of accelerating the computation of PageRank problems, a new method is proposed by preconditioning the MPIO method with an adaptive generalized Arnoldi (GArnoldi) method. The new method is called as an adaptive GArnoldi-MPIO method, whose construction and convergence analysis are discussed in detail. Numerical experiments on several PageRank problems are reported to illustrate the effectiveness of our proposed 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]

In this paper, we study a τ-preconditioner for non-symmetric linear system arising from a steady-state multi-dimensional Riemann-Liouville (RL) fractional diffusion equation. The generalized minimal residual (GMRES) method is applied to solve the preconditioned linear system. Theoretically, we show that the GMRES solver for the preconditioned linear system has a convergence rate independent of discretization stepsizes. To the best of our knowledge, this is the first iterative solver with stepsize-independent convergence rate for the non-symmetric linear system. The proposed τ-preconditioner is diagonalizable by the sine transform matrix, thanks to which the matrix-vector multiplication in each iteration step can be fast implemented by the fast sine transform (FST). Hence, the total operation cost of the proposed solver for the non-symmetric problem is linearithmic. Numerical results are reported to show the efficiency of the proposed preconditioner. [ABSTRACT FROM AUTHOR]

In this paper, by using a modulus-based matrix splitting method as a smoother, a new modulus-based cascadic multigrid method is presented for solving elliptic variational inequality problems. Convergence of the new method is analyzed. Numerical experiments confirm the theoretical analysis and show the efficiency of the proposed method. [ABSTRACT FROM AUTHOR]

In this paper, we exploit the Strang splitting technique for solving the multidimensional Allen-Cahn equations with anisotropic spatial fractional Riesz derivatives. Fully discrete numerical methods are proposed using exponential Strang's splitting schemes for the time integration with finite difference discretization in space. It is proved that the proposed methods can preserve the discrete maximum principle unconditionally. Furthermore, the fully discrete methods are theoretically confirmed to be convergent with second-order accuracy in both of time and space. In practical implementation, the proposed algorithms require to compute the matrix exponential associated with only one-dimensional discretized matrices that possess Toeplitz structure. Meanwhile, a fast algorithm is further developed for evaluating the product of the Toeplitz matrix exponential with a vector. Numerical examples are presented to verify the theoretical analysis and demonstrate the efficiency of the proposed methods. [ABSTRACT FROM AUTHOR]

PageRank is a widespread model for analysing the relative relevance of nodes within large graphs arising in several applications. In the current paper, we present a cost-effective Hessenberg-type method built upon the Hessenberg process for the solution of difficult PageRank problems. The new method is very competitive with other popular algorithms in this field, such as Arnoldi-type methods, especially when the damping factor is close to 1 and the dimension of the search subspace is large. The convergence and the complexity of the proposed algorithm are investigated. Numerical experiments are reported to show the efficiency of the new solver for practical PageRank computations. [ABSTRACT FROM AUTHOR]

In this paper, the block generalized product-type bi-conjugate gradient (GPBi-CG) method for solving large, sparse nonsymmetric linear systems of equations with multiple right-hand sides is proposed. The new algorithm is based on the block BiCG process. We analyze the convergence behavior of this method and present a bound for the residual norm of block GPBi-CG according to the residual norm of Bl-GMRES method. In addition, we prove that convergence is guaranteed when A is positive real. The numerical experiments show the efficiency of the new method and confirm the theoretical results. [ABSTRACT FROM AUTHOR]

Discrete ill-posed inverse problems arise in various areas of science and engineering. The presence of noise in the data often makes it difficult to compute an accurate approximate solution. To reduce the sensitivity of the computed solution to the noise, one replaces the original problem by a nearby well-posed minimization problem, whose solution is less sensitive to the noise in the data than the solution of the original problem. This replacement is known as regularization. We consider the situation when the minimization problem consists of a fidelity term, that is defined in terms of a p-norm, and a regularization term, that is defined in terms of a q-norm. We allow 0 < p,q ≤ 2. The relative importance of the fidelity and regularization terms is determined by a regularization parameter. This paper develops an automatic strategy for determining the regularization parameter for these minimization problems. The proposed approach is based on a new application of generalized cross validation. Computed examples illustrate the performance of the method proposed. [ABSTRACT FROM AUTHOR]

Low-rank Krylov methods are one of the few options available in the literature to address the numerical solution of large-scale general linear matrix equations. These routines amount to well-known Krylov schemes that have been equipped with a couple of low-rank truncations to maintain a feasible storage demand in the overall solution procedure. However, such truncations may affect the convergence properties of the adopted Krylov method. In this paper we show how the truncation steps have to be performed in order to maintain the convergence of the Krylov routine. Several numerical experiments validate our theoretical findings. [ABSTRACT FROM AUTHOR]

Solving large-scale l1 minimization problem is very important and has attracted much attentions in recent years. In this paper, we present an efficient method for solving this problem. To this end, we first reformulate this problem as a nonnegative constrained minimization problem. Then we propose a modulus-based iterative method to solve the nonnegative constrained minimization problem. Convergence analysis and the choice of near optimal parameter are presented. Experimental results are given to illustrate feasibility and effectiveness of our proposed method. [ABSTRACT FROM AUTHOR]

We study a two-dimensional coordinate descent method to solve large linear least squares problems expanding on the method presented by Leventhal and Lewis. For an overdetermined system with full column rank, they proved its convergence in expectation, regardless of its consistency. In our work, we present a block version of the same. We also present an update on the extension done by Ma et al. to address non-full rank linear systems or underdetermined linear systems. Convergence is analyzed for the stated methods, and numerical experiments are provided to demonstrate their efficiency. [ABSTRACT FROM AUTHOR]

In this work, we propose a simple yet generic preconditioned Krylov subspace method for a large class of nonsymmetric block Toeplitz all-at-once systems arising from discretizing evolutionary partial differential equations. Namely, our main result is to propose two novel symmetric positive definite preconditioners, which can be efficiently diagonalized by the discrete sine transform matrix. More specifically, our approach is to first permute the original linear system to obtain a symmetric one and subsequently develop desired preconditioners based on the spectral symbol of the modified matrix. Then, we show that the eigenvalues of the preconditioned matrix sequences are clustered around ± 1 , which entails rapid convergence when the minimal residual method is devised. Alternatively, when the conjugate gradient method on the normal equations is used, we show that our preconditioner is effective in the sense that the eigenvalues of the preconditioned matrix sequence are clustered around unity. An extension of our proposed preconditioned method is given for high-order backward difference time discretization schemes, which can be applied on a wide range of time-dependent equations. Numerical examples are given, also in the variable-coefficient setting, to demonstrate the effectiveness of our proposed preconditioners, which consistently outperforms an existing block circulant preconditioner discussed in the relevant literature. [ABSTRACT FROM AUTHOR]

We develop structure-preserving incomplete LU type factorizations for preconditioning centrosymmetric matrices and use them to numerically solve centrosymmetric and nearly centrosymmetric linear systems arising from spectral methods for partial differential equations. Our algorithm builds in part on direct solution techniques previously developed for this type of linear systems, featuring double-cone factorizations. We illustrate our findings on discretizations of model problems involving the Poisson, diffusion, Helmholtz, and biharmonic equations in one, two, and three dimensions. [ABSTRACT FROM AUTHOR]