On an initial‐boundary value problem for a wide‐angle parabolic equation in a waveguide with a variable bottom

We consider the third‐order Claerbout‐type wide‐angle parabolic equation (PE) of underwater acoustics in a cylindrically symmetric medium consisting of water over a soft bottom B of range‐dependent topography. There is strong indication that the initial‐boundary value problem for this equation with just a homogeneous Dirichlet boundary condition posed on B may not be well‐posed, for example when B is downsloping. We impose, in addition to the above, another homogeneous, second‐order boundary condition, derived by assuming that the standard (narrow‐angle) PE holds on B, and establish a priori H² estimates for the solution of the resulting initial‐boundary value problem for any bottom topography. After a change of the depth variable that makes B horizontal, we discretize the transformed problem by a second‐order accurate finite difference scheme and show, in the case of upsloping and downsloping wedge‐type domains, that the new model gives stable and accurate results. We also present an alternative set of boundary conditions that make the problem exactly energy conserving; one of these conditions may be viewed as a generalization of the Abrahamsson–Kreiss boundary condition in the wide‐angle case. Copyright © 2008 John Wiley & Sons, Ltd.     

A numerical study of 2D integrated RBFNs incorporating Cartesian grids for solving 2D elliptic differential problems

This article reports a numerical discretization scheme, based on two‐dimensional integrated radial‐basis‐function networks (2D‐IRBFNs) and rectangular grids, for solving second‐order elliptic partial differential equations defined on 2D nonrectangular domains. Unlike finite‐difference and 1D‐IRBFN Cartesian‐grid techniques, the present discretization method is based on an approximation scheme that allows the field variable and its derivatives to be evaluated anywhere within the domain and on the boundaries, regardless of the shape of the problem domain. We discuss the following two particular strengths, which the proposed Cartesian‐grid‐based procedure possesses, namely (i) the implementation of Neumann boundary conditions on irregular boundaries and (ii) the use of high‐order integration schemes to evaluate flux integrals arising from a control‐volume discretization on irregular domains. A new preconditioning scheme is suggested to improve the 2D‐IRBFN matrix condition number. Good accuracy and high‐order convergence solutions are obtained. © 2009 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2010     

A finite difference method for the wide‐angle “parabolic” equation in a waveguide with downsloping bottom

We consider the third‐order wide‐angle “parabolic” equation of underwater acoustics in a cylindrically symmetric fluid medium over a bottom of range‐dependent bathymetry. It is known that the initial‐boundary‐value problem for this equation may not be well posed in the case of (smooth) bottom profiles of arbitrary shape, if it is just posed e.g. with a homogeneous Dirichlet bottom boundary condition. In this article, we concentrate on downsloping bottom profiles and propose an additional boundary condition that yields a well‐posed problem, in fact making it L² ‐conservative in the case of appropriate real parameters. We solve the problem numerically by a Crank–Nicolson‐type finite difference scheme, which is proved to be unconditionally stable and second‐order accurate and simulates accurately realistic underwater acoustic problems. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2013     

A comparative study of efficient iterative solvers for generalized Stokes equations

We consider a generalized Stokes equation with problem parameters ξ?0 (size of the reaction term) and ν>0 (size of the diffusion term). We apply a standard finite element method for discretization. The main topic of the paper is a study of efficient iterative solvers for the resulting discrete saddle point problem. We investigate a coupled multigrid method with Braess–Sarazin and Vanka‐type smoothers, a preconditioned MINRES method and an inexact Uzawa method. We present a comparative study of these methods. An important issue is the dependence of the rate of convergence of these methods on the mesh size parameter and on the problem parameters ξ and ν. We give an overview of the main theoretical convergence results known for these methods. For a three‐dimensional problem, discretized by the Hood–Taylor ??₂–??₁ pair, we give results of numerical experiments. Copyright © 2007 John Wiley & Sons, Ltd.     

A balancing domain decomposition by constraints preconditioner for a weakly over‐penalized symmetric interior penalty method

We develop a balancing domain decomposition by constraints preconditioner for a weakly over‐penalized symmetric interior penalty method for second‐order elliptic problems. We show that the condition number of the preconditioned system satisfies similar estimates as those for conforming finite element methods. Corroborating numerical results are also presented. Copyright © 2012 John Wiley & Sons, Ltd.     

Iteratively reweighted algorithm for signals recovery with coherent tight frame

We consider the problem of compressed sensing with a coherent tight frame and design an iteratively reweighted least squares algorithm to solve it. To analyze the problem, we propose a sufficient null space property under a tight frame (sufficient D‐NSP). We show that, if a measurement matrix A satisfies the sufficient D‐NSP of order s, then an s‐sparse signal under the tight frame can be exactly recovered. Furthermore, if A satisfies the restricted isometric property with tight frame D of order 2bs, then it also satisfies the sufficient D‐NSP of order as with a < b and b sufficiently large. We prove the convergence of the algorithm based on the sufficient D‐NSP and give the upper error bounds. In numerical experiments, we use the discrete cosine transform, discrete Fourier transform, and Haar wavelets to verify the effectiveness of this algorithm. With increasing measurement number, the signal‐to‐noise ratio increases monotonically.     

Hybrid,phase–fitted,four–step methods of seventh order for solving x″(t) = f(t,x)

A four‐step method of seventh algebraic order is presented. It is tuned for addressing the special second order initial value problem. The new method is hybrid, explicit, and uses three stages per step. In addition is phase fitted. In consequence it uses variable coefficients that depend on the magnitude of the step‐size. We also present numerical tests on a set of standard problems that illustrate the efficiency of the derived method over older ones given in the relevant literature.     

A modified quasi-boundary value method for ill-posed problems

In this paper, we study a final value problem for first order abstract differential equation with positive self-adjoint unbounded operator coefficient. This problem is ill-posed. Perturbing the final condition we obtain an approximate nonlocal problem depending on a small parameter. We show that the approximate problems are well posed and that their solutions converge if and only if the original problem has a classical solution. We also obtain estimates of the solutions of the approximate problems and a convergence result of these solutions. Finally, we give explicit convergence rates.     

Block s‐step Krylov iterative methods

Block (including s‐step) iterative methods for (non)symmetric linear systems have been studied and implemented in the past. In this article we present a (combined) block s‐step Krylov iterative method for nonsymmetric linear systems. We then consider the problem of applying any block iterative method to solve a linear system with one right‐hand side using many linearly independent initial residual vectors. We present a new algorithm which combines the many solutions obtained (by any block iterative method) into a single solution to the linear system. This approach of using block methods in order to increase the parallelism of Krylov methods is very useful in parallel systems. We implemented the new method on a parallel computer and we ran tests to validate the accuracy and the performance of the proposed methods. It is expected that the block s‐step methods performance will scale well on other parallel systems because of their efficient use of memory hierarchies and their reduction of the number of global communication operations over the standard methods. Copyright © 2009 John Wiley & Sons, Ltd.     

Perturbation analysis for mixed least squares–total least squares problems

In many linear parameter estimation problems, one can use the mixed least squares–total least squares (MTLS) approach to solve them. This paper is devoted to the perturbation analysis of the MTLS problem. Firstly, we present the normwise, mixed, and componentwise condition numbers of the MTLS problem, and find that the normwise, mixed, and componentwise condition numbers of the TLS problem and the LS problem are unified in the ones of the MTLS problem. In the analysis of the first‐order perturbation, we first provide an upper bound based on the normwise condition number. In order to overcome the problems encountered in calculating the normwise condition number, we give an upper bound for computing more effectively for the MTLS problem. As two estimation techniques for solving the linear parameter estimation problems, interesting connections between their solutions, their residuals for the MTLS problem, and the LS problem are compared. Finally, some numerical experiments are performed to illustrate our results.     

Detecting inclusions with a generalized impedance condition from electrostatic data via sampling

In this paper, we derive a sampling method to solve the inverse shape problem of recovering an inclusion with a generalized impedance condition from electrostatic Cauchy data. The generalized impedance condition is a second order differential operator applied to the boundary of the inclusion. We assume that the Dirichlet‐to‐Neumann mapping is given from measuring the current on the outer boundary from an imposed voltage. A simple numerical example is given to show the effectiveness of the proposed inversion method for recovering the inclusion. We also consider the inverse impedance problem of determining the impedance parameters for a known material from the Dirichlet‐to‐Neumann mapping assuming the inclusion has been reconstructed where uniqueness for the reconstruction of the coefficients is proven.     

Hierarchical Schur complement preconditioner for the stochastic Galerkin finite element methods

Use of the stochastic Galerkin finite element methods leads to large systems of linear equations obtained by the discretization of tensor product solution spaces along their spatial and stochastic dimensions. These systems are typically solved iteratively by a Krylov subspace method. We propose a preconditioner, which takes an advantage of the recursive hierarchy in the structure of the global matrices. In particular, the matrices posses a recursive hierarchical two‐by‐two structure, with one of the submatrices block diagonal. Each of the diagonal blocks in this submatrix is closely related to the deterministic mean‐value problem, and the action of its inverse is in the implementation approximated by inner loops of Krylov iterations. Thus, our hierarchical Schur complement preconditioner combines, on each level in the approximation of the hierarchical structure of the global matrix, the idea of Schur complement with loops for a number of mutually independent inner Krylov iterations, and several matrix–vector multiplications for the off‐diagonal blocks. Neither the global matrix nor the matrix of the preconditioner need to be formed explicitly. The ingredients include only the number of stiffness matrices from the truncated Karhunen–Loève expansion and a good preconditioned for the mean‐value deterministic problem. We provide a condition number bound for a model elliptic problem, and the performance of the method is illustrated by numerical experiments. Copyright © 2013 John Wiley & Sons, Ltd.     

Analysis of algebraic systems arising from fourth‐order compact discretizations of convection‐diffusion equations

We study the properties of coefficient matrices arising from high‐order compact discretizations of convection‐diffusion problems. Asymptotic convergence factors of the convex hull of the spectrum and the field of values of the coefficient matrix for a one‐dimensional problem are derived, and the convergence factor of the convex hull of the spectrum is shown to be inadequate for predicting the convergence rate of GMRES. For a two‐dimensional constant‐coefficient problem, we derive the eigenvalues of the nine‐point matrix, and we show that the matrix is positive definite for all values of the cell‐Reynolds number. Using a recent technique for deriving analytic expressions for discrete solutions produced by the fourth‐order scheme, we show by analyzing the terms in the discrete solutions that they are oscillation‐free for all values of the cell Reynolds number. Our theoretical results support observations made through numerical experiments by other researchers on the non‐oscillatory nature of the discrete solution produced by fourth‐order compact approximations to the convection‐diffusion equation. © 2002 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 18: 155–178, 2002; DOI 10.1002/num.1041     

Global attractor for a low order ODE model problem for transition to turbulence

Many researchers have studied simple low order ODE model problems for fluid flows in order to gain new insight into the dynamics of complex fluid flows. We investigate the existence of a global attractor for a low order ODE system that has served as a model problem for transition to turbulence in viscous incompressible fluid flows. The ODE system has a linear term and an energy‐conserving, non‐quadratic nonlinearity. Standard energy estimates show that solutions remain bounded and converge to a global attractor when the linear term is negative definite, that is, the linear term is energy decreasing; however, numerical results indicate the same result is true in some cases when the linear term does not satisfy this condition. We give a new condition guaranteeing solutions remain bounded and converge to a global attractor even when the linear term is not energy decreasing. We illustrate the new condition with examples. Copyright © 2016 John Wiley & Sons, Ltd.     

A box‐shaped cyclically reduced operator

We propose a new procedure of partial cyclic reduction, where we apply a 2^d‐color ordering (with d=2, 3 the dimension of the problem), and use different operators for different gridpoints according to their color. These operators are chosen so that the gridpoints can be readily decoupled, and we then eliminate all colors but one. This yields a smaller cartesian mesh and box‐shaped 9‐point (in 2D) or 27‐point (in 3D) operators that are easy to analyze and implement. Multi‐line and multi‐plane orderings are considered, and we perform convergence analysis and numerical experiments that demonstrate the merits of our approach. Copyright © 2010 John Wiley & Sons, Ltd.     

A nearly optimal preconditioning based on recursive red–black orderings

Considering matrices obtained by the application of a five-point stencil on a 2D rectangular grid, we analyse a preconditioning method introduced by Axelsson and Eijkhout, and by Brand and Heinemann. In this method, one performs a (modified) incomplete factorization with respect to a so-called ‘repeated’ or ‘recursive’ red–black ordering of the unknowns while fill-in is accepted provided that the red unknowns in a same level remain uncoupled. Considering discrete second order elliptic PDEs with isotropic coefficients, we show that the condition number is bounded by 𝒪(n ${}^{\text{½ log}{}_{\text{2}}\text{(√(5) −1)}}$ ) where n is the total number of unknowns (½ log₂(√(5) − 1) = 0.153), and thus, that the total arithmetic work for the solution is bounded by 𝒪(n^1.077). Our condition number estimate, which turns out to be better than standard 𝒪(log² n) estimates for any realistic problem size, is purely algebraic and holds in the presence of Neumann boundary conditions and/or discontinuities in the PDE coefficients. Numerical tests are reported, displaying the efficiency of the method and the relevance of our analysis. © 1997 John Wiley & Sons, Ltd.     

Sampling and multilevel coarsening algorithms for fast matrix approximations

This paper addresses matrix approximation problems for matrices that are large, sparse, and/or representations of large graphs. To tackle these problems, we consider algorithms that are based primarily on coarsening techniques, possibly combined with random sampling. A multilevel coarsening technique is proposed, which utilizes a hypergraph associated with the data matrix and a graph coarsening strategy based on column matching. We consider a number of standard applications of this technique as well as a few new ones. Among standard applications, we first consider the problem of computing partial singular value decomposition, for which a combination of sampling and coarsening yields significantly improved singular value decomposition results relative to sampling alone. We also consider the column subset selection problem, a popular low‐rank approximation method used in data‐related applications, and show how multilevel coarsening can be adapted for this problem. Similarly, we consider the problem of graph sparsification and show how coarsening techniques can be employed to solve it. We also establish theoretical results that characterize the approximation error obtained and the quality of the dimension reduction achieved by a coarsening step, when a proper column matching strategy is employed. Numerical experiments illustrate the performances of the methods in a few applications.     

Computing the matrix geometric mean: Riemannian versus Euclidean conditioning,implementation techniques,and a Riemannian BFGS method

This paper addresses the problem of computing the Riemannian center of mass of a collection of symmetric positive definite matrices. We show in detail that the condition number of the Riemannian Hessian of the underlying optimization problem is never very ill conditioned in practice, which explains why the Riemannian steepest descent approach has been observed to perform well. We also show theoretically and empirically that this property is not shared by the Euclidean Hessian. We then present a limited‐memory Riemannian BFGS method to handle this computational task. We also provide methods to produce efficient numerical representations of geometric objects that are required for Riemannian optimization methods on the manifold of symmetric positive definite matrices. Through empirical results and a computational complexity analysis, we demonstrate the robust behavior of the limited‐memory Riemannian BFGS method and the efficiency of our implementation when compared to state‐of‐the‐art algorithms.     

Minimizing the condition number of a positive definite matrix by completion

Summary. We consider the problem of minimizing the spectral condition number of a positive definite matrix by completion: \noindent where is an Hermitian positive definite matrix, a matrix and is a free Hermitian matrix. We reduce this problem to an optimization problem for a convex function in one variable. Using the minimal solution of this problem we characterize the complete set of matrices that give the minimum condition number. Received October 15, 1993     

Families of arcs on rational surface singularities

We consider the spaceH of arcs on a rational surface singularity (S, P), with the proalgebraic structure induced by the truncation maps. We introduce some sets of arcs by imposing valuative conditions and we prove that they are closed subsets ofH. This leads to give a sufficient condition in order to have an affirmative answer for the problem of Nash. We conclude the solution of the problem for the minimal surface singularities. Supported by D.G.I.C.Y.T. PB91-0210-C02-01