A new Euler matrix method for solving systems of linear Volterra integral equations with variable coefficients

This article develops an efficient solver based on collocation points for solving numerically a system of linear Volterra integral equations (VIEs) with variable coefficients. By using the Euler polynomials and the collocation points, this method transforms the system of linear VIEs into the matrix equation. The matrix equation corresponds to a system of linear equations with the unknown Euler coefficients. A small number of Euler polynomials is needed to obtain a satisfactory result. Numerical results with comparisons are given to confirm the reliability of the proposed method for solving VIEs with variable coefficients.     

An iterative solver for the Oseen problem and numerical solution of incompressible Navier–Stokes equations

Incompressible unsteady Navier–Stokes equations in pressure–velocity variables are considered. By use of the implicit and semi‐implicit schemes presented the resulting system of linear equations can be solved by a robust and efficient iterative method. This iterative solver is constructed for the system of linearized Navier–Stokes equations. The Schur complement technique is used. We present a new approach of building a non‐symmetric preconditioner to solve a non‐symmetric problem of convection–diffusion and saddle‐point type. It is shown that handling the differential equations properly results in constructing efficient solvers for the corresponding finite linear algebra systems. The method has good performance for various ranges of viscosity and can be used both for 2D and 3D problems. The analysis of the method is still partly heuristic, however, the mathematically rigorous results are proved for certain cases. The proof is based on energy estimates and basic properties of the underlying partial differential equations. Numerical results are provided. Additionally, a multigrid method for the auxiliary convection–diffusion problem is briefly discussed. Copyright © 1999 John Wiley & Sons, Ltd.     

The Method of Fundamental Solutions: A Weighted Least-Squares Approach

We investigate the Method of Fundamental Solutions (MFS) for the solution of certain elliptic boundary value problems. In particular, we study the case in which the number of collocation points exceeds the number of singularities, which leads to an over-determined linear system. In such a case, the resulting linear system is over-determined and the proposed algorithm chooses the approximate solution for which the error, when restricted to the boundary, minimizes a suitably defined discrete Sobolev norm. This is equivalent to a weighted least-squares treatment of the resulting over-determined system. We prove convergence of the method in the case of the Laplace’s equation with Dirichlet boundary data in the disk. We develop an alternative way of implementing the numerical algorithm, which avoids the inherent ill-conditioning of the MFS matrices. Finally, we present numerical experiments suggesting that introduction of Sobolev weights improves the approximation. AMS subject classification (2000) 35E05, 35J25, 65N12, 65N15, 65N35, 65T50     

A collocation method for solving a class of singular nonlinear two-point boundary value problems

In this paper, an iterative algorithm for solving singular nonlinear two-point boundary value problems is formulated. This method is basically a collocation method for nonlinear second-order two-point boundary value problems with singularities at either one or both of the boundary points. It is proved that the iterative algorithm converges to a smooth approximate solution of the BVP provided the boundary value problem is well posed and the algorithm is applied appropriately. Error estimates for uniform partitions are also investigated. It has been shown that, for sufficiently smooth solutions, the method produces order h⁴ approximations. Numerical examples are provided to show the effectiveness of the algorithm.     

Splitting methods for second‐order initial value problems

We consider implicit integration methods for the solution of stiff initial value problems for second-order differential equations of the special form y' = f(y). In implicit methods, we are faced with the problem of solving systems of implicit relations. This paper focuses on the construction and analysis of iterative solution methods which are effective in cases where the Jacobian of the right‐hand side of the differential equation can be split into a sum of matrices with a simple structure. These iterative methods consist of the modified Newton method and an iterative linear solver to deal with the linear Newton systems. The linear solver is based on the approximate factorization of the system matrix associated with the linear Newton systems. A number of convergence results are derived for the linear solver in the case where the Jacobian matrix can be split into commuting matrices. Such problems often arise in the spatial discretization of time‐dependent partial differential equations. Furthermore, the stability matrix and the order of accuracy of the integration process are derived in the case of a finite number of iterations. This revised version was published online in August 2006 with corrections to the Cover Date.     

Block iterative solvers for higher order finite volume methods

Recently, new higher order finite volume methods (FVM) were introduced in [Z. Cai, J. Douglas, M. Park, Development and analysis of higher order finite volume methods over rectangles for elliptic equations, Adv. Comput. Math. 19 (2003) 3-33], where the linear system derived by the hybridization with Lagrange multiplier satisfying the flux consistency condition is reduced to a linear system for a pressure variable by an appropriate quadrature rule. We study the convergence of an iterative solver for this linear system. The conjugate gradient (CG) method is a natural choice to solve the system, but it seems slow, possibly due to the non-diagonal dominance of the system. In this paper, we propose block iterative methods with a reordering scheme to solve the linear system derived by the higher order FVM and prove their convergence. With a proper ordering, each block subproblem can be solved by fast methods such as the multigrid (MG) method. The numerical experiments show that these block iterative methods are much faster than CG.     

On an augmented Lagrangian-based preconditioning of Oseen type problems

The paper deals with a general framework for constructing preconditioners for saddle point matrices, in particular as arising in the discrete linearized Navier-Stokes equations (Oseen’s problem). We utilize the so-called augmented Lagrangian framework, where the original linear system of equations is first transformed to an equivalent one, which latter is then solved by a preconditioned iterative solution method.     

On the stability of functionally fitted Runge–Kutta methods

Classical collocation RK methods are polynomially fitted in the sense that they integrate an ODE problem exactly if its solution is an algebraic polynomial up to some degree. Functionally fitted RK (FRK) methods are collocation techniques that generalize this principle to solve an ODE problem exactly if its solution is a linear combination of a chosen set of arbitrary basis functions. Given for example a periodic or oscillatory ODE problem with a known frequency, it might be advantageous to tune a trigonometric FRK method targeted at such a problem. However, FRK methods lead to variable coefficients that depend on the parameters of the problem, the time, the stepsize, and the basis functions in a non-trivial manner that inhibits any in-depth analysis of the behavior of the methods in general. We present the class of so-called separable basis functions and show how to characterize the stability function of the methods in this particular class. We illustrate this explicitly with an example and we provide further insight for separable methods with symmetric collocation points. AMS subject classification (2000) 65L05, 65L06, 65L20, 65L60     

A stable primal–dual approach for linear programming under nondegeneracy assumptions

This paper studies a primal–dual interior/exterior-point path-following approach for linear programming that is motivated on using an iterative solver rather than a direct solver for the search direction. We begin with the usual perturbed primal–dual optimality equations. Under nondegeneracy assumptions, this nonlinear system is well-posed, i.e. it has a nonsingular Jacobian at optimality and is not necessarily ill-conditioned as the iterates approach optimality. Assuming that a basis matrix (easily factorizable and well-conditioned) can be found, we apply a simple preprocessing step to eliminate both the primal and dual feasibility equations. This results in a single bilinear equation that maintains the well-posedness property. Sparsity is maintained. We then apply either a direct solution method or an iterative solver (within an inexact Newton framework) to solve this equation. Since the linearization is well posed, we use affine scaling and do not maintain nonnegativity once we are close enough to the optimum, i.e. we apply a change to a pure Newton step technique. In addition, we correctly identify some of the primal and dual variables that converge to 0 and delete them (purify step). We test our method with random nondegenerate problems and problems from the Netlib set, and we compare it with the standard Normal Equations NEQ approach. We use a heuristic to find the basis matrix. We show that our method is efficient for large, well-conditioned problems. It is slower than NEQ on ill-conditioned problems, but it yields higher accuracy solutions.     

A Jacobi-Davidson method for two real parameter nonlinear eigenvalue problems arising from delay differential equations

The critical delays of a delay-differential equation can be computed by solving a nonlinear two-parameter eigenvalue problem. For large scale problems, we propose new correction equations for a Jacobi-Davidson type method, that also forces real valued critical delays. We present two different equations: one complex valued equation using a direct linear system solver, and one Jacobi-Davidson style correction equation which is suitable for an iterative linear system solver. A numerical example of a large scale problem arising from PDEs shows the effectiveness of the method. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the convergence of right transforming iterations for the numerical solution of PDE‐constrained optimization problems

We present an iterative solver, called right transforming iterations (or right transformations), for linear systems with a certain structure in the system matrix, such as they typically arise in the framework of Karush–Kuhn–Tucker (KKT) conditions for optimization problems under PDE constraints. The construction of the right transforming scheme depends on an inner approximate solver for the underlying PDE subproblems. We give a rigorous convergence proof for the right transforming iterative scheme in dependence on the convergence properties of the inner solver. Provided that a fast subsolver is available, this iterative scheme represents an efficient way of solving first‐order optimality conditions. Numerical examples endorse the theoretically predicted contraction rates. Copyright © 2011 John Wiley & Sons, Ltd.     

Interior-Point Solver for Large-Scale Quadratic Programming Problems with Bound Constraints

In this paper, we present an interior-point algorithm for large and sparse convex quadratic programming problems with bound constraints. The algorithm is based on the potential reduction method and the use of iterative techniques to solve the linear system arising at each iteration. The global convergence properties of the potential reduction method are reassessed in order to take into account the inexact solution of the inner system. We describe the iterative solver, based on the conjugate gradient method with a limited-memory incomplete Cholesky factorization as preconditioner. Furthermore, we discuss some adaptive strategies for the fill-in and accuracy requirements that we use in solving the linear systems in order to avoid unnecessary inner iterations when the iterates are far from the solution. Finally, we present the results of numerical experiments carried out to verify the effectiveness of the proposed strategies. We consider randomly generated sparse problems without a special structure. Also, we compare the proposed algorithm with the MOSEK solver. Research partially supported by the MIUR FIRB Project RBNE01WBBB “Large-Scale Nonlinear Optimization.”     

The combination of collocation,finite difference,and multigrid methods for solution of the two‐dimensional wave equation

In this article, we apply compact finite difference approximations of orders two and four for discretizing spatial derivatives of wave equation and collocation method for the time component. The resulting method is unconditionally stable and solves the wave equation with high accuracy. The solution is approximated by a polynomial at each grid point that its coefficients are determined by solving a linear system of equations. We employ the multigrid method for solving the resulted linear system. Multigrid method is an iterative method which has grid independently convergence and solves the linear system of equations in small amount of computer time. Numerical results show that the compact finite difference approximation of fourth order, collocation and multigrid methods produce a very efficient method for solving the wave equation. © 2007 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2008     

On Global Convergence and Approximate Iteration of the Linear Approximation Method for Solving Variational Inequalities

This paper is concerned with the linear approximation method (i.e. the iterative method in which a sequence of vectors is generated by solving certain linearized subproblems) for solving the variational inequality. The global convergent iterative process is proposed by applying the continuation method, and the related problems are discussed. A convergent result is obtained for the approximation iteration (i.e. the iterative method in which a sequence of vectors is generated by solving certain linearized subproblems approximately).     

A Jacobi–Davidson method for two‐real‐parameter nonlinear eigenvalue problems arising from delay‐differential equations

The critical delays of a delay‐differential equation can be computed by solving a nonlinear two‐parameter eigenvalue problem. The solution of this two‐parameter problem can be translated to solving a quadratic eigenvalue problem of squared dimension. We present a structure preserving QR‐type method for solving such quadratic eigenvalue problem that only computes real‐valued critical delays; that is, complex critical delays, which have no physical meaning, are discarded. For large‐scale problems, we propose new correction equations for a Newton‐type or Jacobi–Davidson style method, which also forces real‐valued critical delays. We present three different equations: one real‐valued equation using a direct linear system solver, one complex valued equation using a direct linear system solver, and one Jacobi–Davidson style correction equation that is suitable for an iterative linear system solver. We show numerical examples for large‐scale problems arising from PDEs. Copyright © 2012 John Wiley & Sons, Ltd.     

An accelerated Poisson solver based on multidomain spectral discretization

This paper presents a numerical method for variable coefficient elliptic PDEs with mostly smooth solutions on two dimensional domains. The method works best for domains that can readily be mapped onto a rectangle, or a collection of nonoverlapping rectangles. The PDE is discretized via a multi-domain spectral collocation method of high local order (order 30 and higher have been tested and work well). Local mesh refinement results in highly accurate solutions even in the presence of local irregular behavior due to corner singularities, localized loads, etc. The system of linear equations attained upon discretization is solved using a direct (as opposed to iterative) solver with \(O(N^{1.5})\) complexity for the factorization stage and \(O(N \log N)\) complexity for the solve. The scheme is ideally suited for executing the elliptic solve required when parabolic problems are discretized via time-implicit techniques. In situations where the geometry remains unchanged between time-steps, very fast execution speeds are obtained since the solution operator for each implicit solve can be pre-computed.     

The generalized Dirichlet–Neumann map for linear elliptic PDEs and its numerical implementation

A new approach for analyzing boundary value problems for linear and for integrable nonlinear PDEs was introduced in Fokas [A unified transform method for solving linear and certain nonlinear PDEs, Proc. Roy. Soc. London Ser. A 53 (1997) 1411–1443]. For linear elliptic PDEs, an important aspect of this approach is the characterization of a generalized Dirichlet to Neumann map: given the derivative of the solution along a direction of an arbitrary angle to the boundary, the derivative of the solution perpendicularly to this direction is computed without solving on the interior of the domain. This is based on the analysis of the so-called global relation, an equation which couples known and unknown components of the derivative on the boundary and which is valid for all values of a complex parameter k. A collocation-type numerical method for solving the global relation for the Laplace equation in an arbitrary bounded convex polygon was introduced in Fulton et al. [An analytical method for linear elliptic PDEs and its numerical implementation, J. Comput. Appl. Math. 167 (2004) 465–483]. Here, by choosing a different set of the “collocation points” (values for k), we present a significant improvement of the results in Fulton et al. [An analytical method for linear elliptic PDEs and its numerical implementation, J. Comput. Appl. Math. 167 (2004) 465–483]. The new collocation points lead to well-conditioned collocation methods. Their combination with sine basis functions leads to a collocation matrix whose diagonal blocks are point diagonal matrices yielding efficient implementation of iterative methods; numerical experimentation suggests quadratic convergence. The choice of Chebyshev basis functions leads to higher order convergence, which for regular polygons appear to be exponential.     

Null Space Algorithm and Spanning Trees in Solving Darcy's Equation

A Null Space algorithm is considered to solve the augmented system produced by the mixed finite element approximation of Darcy's Law. The method is based on the combination of a LU factorization technique for sparse matrices with an iterative Krylov solver. The computational efficiency of the method relies on the use of spanning trees to compute the LU factorization without fill-in and on a suitable stopping criterion for the iterative solver. We experimentally investigate its performance on a realistic set of selected application problems.This revised version was published online in October 2005 with corrections to the Cover Date.     

A matrix decomposition MFS algorithm for axisymmetric biharmonic problems

We consider the approximate solution of axisymmetric biharmonic problems using a boundary-type meshless method, the Method of Fundamental Solutions (MFS) with fixed singularities and boundary collocation. For such problems, the coefficient matrix of the linear system defining the approximate solution has a block circulant structure. This structure is exploited to formulate a matrix decomposition method employing fast Fourier transforms for the efficient solution of the system. The results of several numerical examples are presented. AMS subject classification 65N38, 65F30, 65T50, 65Y99     

Solution of lambda-omega systems: Theta-schemes and multigrid methods

Summary. The numerical solution of a time-dependent reaction diffusion lambda-omega system discretized by theta-schemes and finite differences is considered. Stability and accuracy of finite difference theta-schemes for this system are established. To solve the time-implicit evolution equations a nonlinear multigrid method is applied. The convergence properties of this solver are investigated considering a linearized lambda-omega model.Mathematics Subject Classification (1991): 35K57, 65M06, 65M12, 65M55, 65P20, 65P40Revised version received February 3, 2004