Search

In this paper we consider domain decomposition methods for solving the radial basis function interpolation equations. There are three interwoven threads to the paper. The first thread provides good ways of setting up and solving small- to medium-sized radial basis function interpolation problems. These may occur as subproblems in a domain decomposition solution of a larger interpolation problem. The usual formulation of such a problem can suffer from an unfortunate scale dependence not intrinsic in the problem itself. This scale dependence occurs, for instance, when fitting polyharmonic splines in even dimensions. We present and analyze an alternative formulation, available for all strictly conditionally positive definite basic functions, which does not suffer from this drawback, at least for the very important example previously mentioned. This formulation changes the problem into one involving a strictly positive definite symmetric system, which can be easily and efficiently solved by Cholesky factorization. The second section considers a natural domain decomposition method for the interpolation equations and views it as an instance of von Neumann's alternating projection algorithm. Here the underlying Hilbert space is the reproducing kernel Hilbert space induced by the strictly conditionally positive definite basic function. We show that the domain decomposition method presented converges linearly under very weak nondegeneracy conditions on the possibly overlapping subdomains. The last section presents some algorithmic details and numerical results of a domain decomposition interpolatory code for polyharmonic splines in 2 and 3 dimensions. This code has solved problems with 5 million centers and can fit splines with 10,000 centers in approximately 7 seconds on very modest hardware. [ABSTRACT FROM AUTHOR]

In this paper we study the performance of time-splitting spectral approximations for general nonlinear Schrödinger equations (NLS) in the semiclassical regimes, where the Planck constant ε is small. The time-splitting spectral approximation under study is explicit, unconditionally stable and conserves the position density in L¹. Moreover it is time-transverse invariant and time-reversible when the corresponding NLS is. Extensive numerical tests are presented for weak/strong focusing/defocusing nonlinearities, for the Gross­Pitaevskii equation, and for current-relaxed quantum hydrodynamics. The tests are geared towards the understanding of admissible meshing strategies for obtaining “correct” physical observables in the semiclassical regimes. Furthermore, comparisons between the solutions of the NLS and its hydrodynamic semiclassical limit are presented. [ABSTRACT FROM AUTHOR]

In this paper we consider the Procrustes problem on the manifold of orthogonal Stiefel matrices. Given matrices A ∈ Rm ×k, B ∈ Rm ×p , m ≥ p ≥ k, we seek the minimum of . A-BQ. 2 for all matrices Q ∈ Rp×k , QTQ = Ik×k . We introduce a class of relaxation methods for generating sequences of approximations to a minimizer and offer a geometric interpretation of these methods. Results of numerical experiments illustrating the convergence of the methods are given. [ABSTRACT FROM AUTHOR]

In this paper we present the cyclic low-rank Smith method, which is an iterative method for the computation of low-rank approximations to the solution of large, sparse, stable Lyapunov equations. It is based on a generalization of the classical Smith method and profits by the usual low-rank property of the right-hand side matrix. The requirements of the method are moderate with respect to both computational cost and memory. Furthermore, we propose a heuristic for determining a set of suboptimal alternating direction implicit (ADI) shift parameters. This heuristic, which is based on a pair of Arnoldi processes, does not require any a priori knowledge on the spectrum of the coefficient matrix of the Lyapunov equation. Numerical experiments show the efficiency of the iterative scheme combined with the heuristic for the ADI parameters. [ABSTRACT FROM AUTHOR]

Multidimensional positive definite advection transport algorithm (MPDATA) is an iterative process for approximating the advection equation, which uses a donor cell approximation to compensate for the truncation error of the originally specified donor cell scheme. This step may be repeated an arbitrary number of times, leading to successively more accurate solutions to the advection equation. In this paper, we show how to sum the successive approximations analytically to find a single antidiffusive velocity that represents the effects of an arbitrary number of passes. The analysis is first done in one dimension to illustrate the method and then is repeated in two dimensions. The existence of cross terms in the truncation analysis of the two-dimensional equations introduces an extra complication into the calculation. We discuss the implementation of our new antidiffusive velocities and provide some examples of applications, including a third-order accurate scheme. [ABSTRACT FROM AUTHOR]

In this paper we describe and analyze a class of nonlinear multiresolution schemes for the multiresolution setting which corresponds to discretization by local averages with respect to the hat function. These schemes are based on the essentially-non-oscillatory (ENO) interpolatory procedure described in [A. Harten, B. Engquist, S. Osher, and S. Chakravarthy, J. Comput. Phys., 71 (1987), pp. 231–302]. We show that by allowing the approximation to fit the local nature of the data, one can improve the compression capabilities of the multiresolution algorithms. The question of stability for nonlinear (data-dependent) reconstruction techniques is also addressed. [ABSTRACT FROM AUTHOR]

We introduce AMGe, an algebraic multigrid method for solving the discrete equations that arise in Ritz-type finite element methods for partial differential equations. Assuming access to the element stiffness matrices, we have that AMGe is based on the use of two local measures, which are derived from global measures that appear in existing multigrid theory. These new measures are used to determine local representations of algebraically ‘smooth’ error components that provide the basis for constructing effective interpolation and, hence, the coarsening process for AMG. Here, we focus on the interpolation process; choice of the coarse ‘grids’ based on these measures is the subject of current research. We develop a theoretical foundation for AMGe and present numerical results that demonstrate the efficacy of the method. [ABSTRACT FROM AUTHOR]

A Legendre spectral Galerkin method is presented for the solution of the biharmonic Dirichlet problem on a square. The solution and its Laplacian are approximated using the set of basis functions suggested by Shen, which are linear combinations of two Legendre polynomials. A Schur complement approach is used to reduce the resulting linear system to one involving the approximation of the Laplacian of the solution on the two vertical sides of the square. The Schur complement system is solved by a preconditioned conjugate gradient method or the Cholesky method. The total cost of the algorithm is O(N3). Numerical results demonstrate the spectral convergence of the method. [ABSTRACT FROM AUTHOR]

A least-squares mixed finite element formulations is applied to the nonlinear elliptic problems arising in each time-step of an implicit Euler discretization for variably saturated flow problems. This approach simultaneously constructs approximations to the flux in Raviart-Thomas spaces and to the hydraulic potential by standard H¹-conforming linear finite elements. Two important properties of the least-squares approach are investigated in detail: the local least-squares functional provides an a posteriori error estimator and Gauss-Newton methods are robust iterative solvers for the resulting nonlinear least-squares problems. Computational experiments conducted for a realistic water table recharge problem illustrate the effectiveness of this approach. [ABSTRACT FROM AUTHOR]

The influence of reorderings on the performance of factorized sparse approximate inverse preconditioners is considered. Some theoretical results on the effect of orderings on the fill-in and decay behavior of the inverse factors of a sparse matrix are presented. It is shown experimentally that certain reorderings, like minimum degree and nested dissection, can be very beneficial. The benefit consists of a reduction in the storage and time required for constructing the preconditioner, and of faster convergence of the preconditioned iteration in many cases of practical interest. [ABSTRACT FROM AUTHOR]

For computation of chemically reacting flows, algorithms are proposed based on appoximations of the Boltzmann equations for gas mixtures. Finite-difference gas-dynamics schemes are constructed and applied to simulate viscous supersonic flows around two-dimensional bodies. An efficient procedure has been developed, permitting one to calculate the influence of chemical reactions on the flow. [ABSTRACT FROM AUTHOR]

A reformulation of the usual least-squares waveform inversion problem is proposed to retrieve, from seismic data, the kinematic parameters (the two-dimensional (2D) background velocity and the source and cable depth) by local optimization. These last parameters are of paramount importance for a successful inversion of very high resolution (VHR) seismic data which we are interested in. In our inversion the source and cable depth parameters are treated in the same way as the background velocity. To avoid the problem of local minima, a change of unknowns is performed: the depth reflectivity is replaced by its dual variable, called the time reflectivity. In this way, the current value of the reflectivity is stored in the time domain and is strongly decoupled from the current value of the velocity field and cable depth. The increase in modeling complexity (an additional prestack migration is required for each function evaluation) is compensated by the enlargement of the attraction domain of the global minimum which allows the use of a local optimization technique. A numerical implementation with Born approximation and ray tracing is detailed, in which the derivatives of the travel time are computed via an adjoint state technique for more efficiency. Numerical results illustrate the behavior of the new objective function, and inversion of synthetic and real VHR data for kinematic parameters is performed. [ABSTRACT FROM AUTHOR]

The accuracy deficiency of high-order conventional finite difference schemes in the high-frequency range is attributed to the approximation property of a power polynomial interpolation over equispaced nodes. To improve the numerical representation of high-frequency solutions, a new family of high-order finite difference schemes is constructed by trigonometric polynomial interpolation. As expected, these new difference schemes can resolve a wider frequency range than conventional finite difference schemes with the same stencil. In particular, they remove the possibility of Runge's phenomenon for uniform mesh. The recently proposed optimized difference schemes are indeed types of mixed difference schemes which make a compromise between power and trigonometric polynomial interpolation. [ABSTRACT FROM AUTHOR]

We present a numerical study of the axisymmetric Couette­Taylor problem using a finite difference scheme. The scheme is based on a staggered version of a second-order central-differencing method combined with a discrete Hodge projection. The use of central-differencing operators obviates the need to trace the characteristic flow associated with the hyperbolic terms. The result is a simple and efficient scheme which is readily adaptable to other geometries and to more complicated flows. The scheme exhibits competitive performance in terms of accuracy, resolution, and robustness. The numerical results agree accurately with linear stability theory and with previous numerical studies. [ABSTRACT FROM AUTHOR]