SSOR-like methods for saddle point problems

Saddle point problems arise in a wide variety of applications in computational and engineering. The aim of this paper is to present a SSOR-like iterative method for solving the saddle point problems. Here the convergence of this method is studied and specifically, the spectral radius and the optimal relaxation parameter of the iteration matrix are also investigated. Numerical experiments show that the SSOR-like method with a proper preconditioning matrix is better than SOR-like method presented by Golub et al. [G.H. Golub, X. Wu, and J.-Y. Yuan, SOR-like methods for augmented systems, BIT 41 (2001), pp. 71–85].     

Two-parameter GSOR method for the augmented system

A new iterative method is given for the augmented system of equations. Similarly to the GSOR and SOR-like methods, the new method involves two iteration parameters and one preconditioning matrix. The convergence analysis and the determination of the optimum parameters are studied first. Then the explicit formulae for the optimum parameters and the associated spectral radius are derived. Finally, numerical computations are presented which show clearly that the new method has a very good numerical performance and is much faster than the SOR-like method.     

Restarted GMRES augmented with harmonic Ritz vectors for shifted linear systems

Frommer and Glassner [Frommer, A. and Glassner, U., 1998, Restarted GMRES for shifted linear systems, SIAM Journal on Scientific Computing, 19, 15–26.] develop a variant of the restarted GMRES method for shifted linear systems at the expense of only one matrix–vector multiplication per iteration. However, restarting slows down the convergence, even stagnation. We present a variant of the restarted GMRES augmented with some approximate eigenvectors for the shifted systems. The convergence can be much faster at little extra expense. Numerical experiments show its efficiency.     

Quotient convergence and multi-splitting methods for solving singular linear equations

Abstract   In this paper, we use the group inverse to characterize the quotient convergence of an iterative method for solving consistent singular linear systems, when the matrix index equals one. Next, we show that for stationary splitting iterative methods, the convergence and the quotient convergence are equivalent, which was first proved in [7]. Lastly, we propose a (multi-)splitting iterative method A=F–G, where the splitting matrix F may be singular, endowed with group inverse, by using F ^# as a solution tool for any iteration. In this direction, sufficient conditions for the quotient convergence of these methods are given. Then, by using the equivalence between convergence and quotient convergence, the classical convergence of these methods is proved. These latter results generalize Cao’s result, which was given for nonsingular splitting matrices F. Keywords: Group inverse, singular linear equations, iterative method, P-regular splitting, Hermitian positive definite matrix, multi-splitting, quotient convergence AMS Classification: 15A09, 65F35     

Fast algorithms for high-order numerical methods for space-fractional diffusion equations

In this paper, fast numerical methods for solving space-fractional diffusion equations are studied in two stages. Firstly, a fast direct solver for an implicit finite difference scheme proposed by Hao et al. [A fourth-order approximation of fractional derivatives with its applications, J. Comput. Phys. 281 (2015), pp. 787–805], which is fourth-order accurate in space and second-order accurate in time, is developed based on a circulant-and-skew-circulant (CS) representation of Toeplitz matrix inversion. Secondly, boundary value method with spatial discretization of Hao et al. [A fourth-order approximation of fractional derivatives with its applications, J. Comput. Phys. 281 (2015), pp. 787–805] is adopted to produce a numerical solution with higher order accuracy in time. Particularly, a method with fourth-order accuracy in both space and time can be achieved. GMRES method is employed for solving the discretized linear system with two preconditioners. Based on the CS representation of Toeplitz matrix inversion, the two preconditioners can be applied efficiently, and the convergence rate of the preconditioned GMRES method is proven to be fast. Numerical examples are given to support the theoretical analysis.     

A class of approximate inverse preconditioners for solving linear systems

Some preconditioners for accelerating the classical iterative methods are given in Zhang et al. [Y. Zhang and T.Z. Huang, A class of optimal preconditioners and their applications, Proceedings of the Seventh International Conference on Matrix Theory and Its Applications in China, 2006. Y. Zhang, T.Z. Huang, and X.P. Liu, Modified iterative methods for nonnegative matrices and M-matrices linear systems, Comput. Math. Appl. 50 (2005), pp. 1587–1602. Y. Zhang, T.Z. Huang, X.P. Liu, A class of preconditioners based on the (I+S(α))-type preconditioning matrices for solving linear systems, Appl. Math. Comp. 189 (2007), pp. 1737–1748]. Another kind of preconditioners approximating the inverse of a symmetric positive definite matrix was given in Simons and Yao [G. Simons, Y. Yao, Approximating the inverse of a symmetric positive definite matrix, Linear Algebra Appl. 281 (1998), pp. 97–103]. Zhang et al. ’s preconditioners and Simons and Yao's are generalized in this paper. These preconditioners are all of low construction cost, which all could be taken as approximate inverse of M-matrices. Numerical experiments of these preconditioners applied with Krylov subspace methods show the effectiveness and performance, which also show that the preconditioners proposed in this paper are better approximate inverse for M-matrices than Simons’.     

Modified iterative methods for nonnegative matrices and M-matrices linear systems

The purpose of this paper is to present new preconditioning techniques for solving nonnegative matrices linear system and M-matrices linear system Ax = b based on the I + S(α) type preconditioning matrices provided by Hadjidimos et al. ^[1] and Evans et al. ^[2]. Convergence analysis of the proposed methods are given. Numerical results are presented, which show the improvements on the convergence rate of the Jacobi type and Gauss-Seidel type preconditioned iterative methods.     

大位移变分光流计算的快速算法

目的 多尺度方法的提出解决了传统HS（Horn Schunck）算法不能计算大位移光流的问题,但同时也增加了迭代运算的步数。为加快迭代收敛速度,研究大位移变分光流计算的快速算法,并分析其性能。方法 将用于加快变分图像处理迭代运算的Split Bregman方法、对偶方法和交替方向乘子法应用到大位移光流计算中。结果 分别进行了精度、迭代步数、运行时间的对比实验。引入3种快速方法的模型均能够在保证精度的同时,在较少时间内计算出图像序列的光流场,所需时间为传统方法的11%~42%。结论 将3种快速方法应用到大位移变分光流计算中,对于不同图像序列均可以较大地提高计算效率。     

Solving inverse eigenvalue problems by a projected Newton method

The inverse eigenvalue problem for symmetric matrices (IEP) can be formulated as a system of two matrix equations. For solving the system a variation of Newton's method is used which has been proposed by Fusco and Zecca [Calcolo XXIII (1986), pp. 285–303] for the simultaneous computation of eigenvalues and eigenvectors of a given symmetric matrix. An iteration step of this method consists of a Newton step followed by an orthonormalization with the consequence that each iterate satisfies one of the given equations. The method is proved to convergence locally quadratically to regular solutions. The algorithm and some numerical examples are presented. In addition, it is shown that the so-called Method III proposed by Friedland, Nocedal, and Overton [SIAM J. Numer. Anal., 24 (1987), pp. 634–667] for solving IEP may be constructed similarly to the method presented here.     

Numerical Solutions to Dynamic Portfolio Problems: The Case for Value Function Iteration using Taylor Approximation

In a recent paper, van Binsbergen and Brandt (Computational Economics, 29, 355–367, 2007), using the method of Brandt et al. (Review of Financial Studies, 18, 831–873, 2005), argue, in the context of a portfolio choice problem with CRRA preferences, that value function iteration (VFI) is inferior to portfolio weight iteration (PWI), when a Taylor approximation is used. In particular, they report that the value function iteration produces highly inaccurate solutions when risk aversion is high and the investment horizon long. We argue that the reason for the deterioration of VFI is the high nonlinearity of the value function and illustrate that if one uses a natural and economically-motivated transformation of the value function, namely the certainty equivalent, the VFI approach produces very accurate results.     

An augmented Lagrangian optimization method for inflatable structures analysis problems

This paper describes the development of an augmented Lagrangian optimization method for the numerical simulation of the inflation process in the design of inflatable space structures. Although the Newton–Raphson scheme was proven to be efficient for solving many nonlinear problems, it can lead to lack of convergence when it is applied to the simulation of the inflation process. As a result, it is recommended to use an optimization algorithm to find the minimum energy configuration that satisfies the equilibrium equations characterizing the final shape of the inflated structure subject to an internal pressure. On top of that, given that some degrees of freedom may be linked, the optimum may be constrained, and specific optimization methods for constrained problems must be considered. The paper presents the formulation and the augmented Lagrangian method (ALM) developed in SAMCEF Mecano for inflatable structures analysis problems. The related quasi-unconstrained optimization problem is solved with a nonlinear conjugate gradient method. The Wolfe conditions are used in conjunction with a cubic interpolation for the line search. Equality constraints are considered and can be easily treated by the ALM formulation. Numerical applications present simulations of unconstrained and constrained inflation processes (i.e., where the motion of some nodes is ruled by a rigid body element restriction and/or problems including contact conditions).Part of this paper was presented at the sixth world congress of Structural and Multidisciplinary Optimization held in Rio de Janeiro, June 2005.     

An iteration method with maximal order based on standard information

For finding a root of a function f, Halley's iteration family is a higher generalization of Newton's iteration function. In every step, it uses the values of f and its first number of derivatives, called standard information. Based on the standard information, we obtain an iteration method with maximal order of convergence. It is a natural generalization of Halley's iteration family in terms of divided differences. An explicit construction for this method is also obtained. Numerical experiments are given demonstrating the importance of the proposed approach.     

On a boundary value method for computing Sturm–Liouville potentials from two spectra

Convergence of a boundary value method (BVM) in Aceto et al. [Boundary value methods for the reconstruction of Sturm–Liouville potentials, Appl. Math. Comput. 219 (2012), pp. 2960–2974] for computing Sturm–Liouville potentials from two spectra is discussed. In Aceto et al. (2012), a continuous approximation of the unknown potential belonging to a suitable function space of finite dimension is obtained by forming an associated set of nonlinear equations and solving these with a quasi-Newton approach. In our paper, convergence of the quasi-Newton approach is established and convergence of the estimate of the unknown potential, provided by the exact solution of the nonlinear equation, to the true potential is proved. To further investigate the properties of the BVM in Aceto et al. (2012), some other spaces of functions are introduced. Numerical examples confirm the theoretically predicted convergence properties and show the accuracy and stability of the BVM.     

Contaminant transport with adsorption and their inverse problems

In Constales et al. (water Resources Res. 39(30), 1303, 2003) dual-well tests are used to reconstruct the flow and dispersion parameters in contaminant transport. A tracer is introduced by the injection well, which is considered to be in steady-state regime with the extraction well. Then, from measurements of the time evolution of the extracted tracer (breakthrough curve) the required model data has been recovered. In Constales et al. (water Resources Res. 39(30), 1303, 2003), a very precise numerical method has been developed for the solution of the direct problem. In Kačur et al. (Comput. Meth. Appl. Mech. Engo. 194(2–5), 479–489, 2005); Remešiková (J. Comp. Appl. Math. 169(1), 101–116, 2004) an extension has been discussed which adds adsorption terms to the model. The inverse problem of determination of sorption isotherms in nonequilibrium mode was solved by a Levenberg–Marquardt iteration method. In the present paper we develop the adjoint system to evaluate the sensitivity of the solution (via the breakthrough curve) on the sorption parameters in equilibrium and nonequilibrium modes. Possible use of the adjoint system in determining the several parameters occuring in the model is a crucial point for iteration methods. The obtained model parameters then can be used in a 3D flow and transport model with adsorption. The numerical experiments we present, justify the used method.     

Two-Dimensional Extension of the Reservoir Technique for Some Linear Advection Systems

In this paper we present an extension of the reservoir technique (see, [Alouges et al., Submitted; Alouges et al.(2002a), In: Finite volumes for complex applications, III, pp. 247–254, Marseille; Alouges et al.(2002b), C. R. Math. Acad. Sci. Paris, 335(7), 627–632.]) for two-dimensional advection equations with non-constant velocities. The purpose of this work is to make decrease the numerical diffusion of finite volume schemes, correcting the numerical directions of propagation, using a so-called corrector vector combined with the reservoirs. We then introduce an object called velocities rose in order to minimize the algorithmic complexity of this method.     

A Unified Primal-Dual Algorithm Framework Based on Bregman Iteration

In this paper, we propose a unified primal-dual algorithm framework for two classes of problems that arise from various signal and image processing applications. We also show the connections to existing methods, in particular Bregman iteration (Osher et al., Multiscale Model. Simul. 4(2):460–489, 2005) based methods, such as linearized Bregman (Osher et al., Commun. Math. Sci. 8(1):93–111, 2010; Cai et al., SIAM J. Imag. Sci. 2(1):226–252, 2009, CAM Report 09-28, UCLA, March 2009; Yin, CAAM Report, Rice University, 2009) and split Bregman (Goldstein and Osher, SIAM J. Imag. Sci., 2, 2009). The convergence of the general algorithm framework is proved under mild assumptions. The applications to ℓ ¹ basis pursuit, TV−L ² minimization and matrix completion are demonstrated. Finally, the numerical examples show the algorithms proposed are easy to implement, efficient, stable and flexible enough to cover a wide variety of applications.     

Some new preconditioned generalized AOR methods for generalized least-squares problems

Some new preconditioned GAOR methods for solving generalized least-squares problems and their comparison results are given. Comparison results show that the convergence rates of the new preconditioned GAOR methods are better than those of the preconditioned GAOR methods presented by Shen et al. [Preconditioned iterative methods for solving weighted linear least squares problems, Appl. Math. Mech. – Engl. Ed. 33(3) (2012), pp. 375–384] whenever these methods are convergent. Lastly, numerical experiments are provided to confirm the theoretical results.     

Iterated Fast Collocation Methods for Integral Equations of the Second Kind

In this paper a new iteration technique is proposed based on fast multiscale collocation methods of Chen et al. (SIAM J Numer Anal 40:344–375, 2002) for Fredholm integral equations of the second kind. It is shown that an additional order of convergence is obtained for each iteration even if the exact solution of the integral equation is non-smooth, the kernel of the integral operator is weakly singular and the matrix compression is implemented. When the solution is smooth, this leads to superconvergence. Numerical examples are presented to illustrate the theoretical results and the efficiency of the method.     

Solving linear systems in interior-point methods

There are two approaches to solve the linear systems in interior-point methods: the normal equation approach and the augmented system approach. We integrated the two methods by applying matrix partitioning to the augmented system approach. Specifically, we show the Schur complement method which is applied to problems with dense columns is a special case of the augmented system approach. We will use this property for the integrated approach. If we use the integrated approach, we can solve linear systems maintaining sparsity of matrices without respect of the existence of dense columns.Scope and purposeInterior-point methods require a step to solve the linear systems for computing a new direction at every iteration. Generally, we solve the linear systems by applying Cholesky factorization. When there is a dense column, we can not exploit the sparsity of matrices. The most popular way of treating such a dense column employs the Schur complement method or the augmented system approach. The Schur complement method is faster than the augmented system approach, but suffers from numerical unstability. We present a fast and numerically stable approach by integrating former approaches.