Search

Let F be a compact set of a Banach space X. This paper analyzes the "generalized empirical interpolation method," which, given a function f ∊ F, builds an interpolant Jn[f] in an n dimensional subspace Xn ⊂ X with the knowledge of n outputs (σi(f))ni=1, where σi ∊ X' and X' is the dual space of X. The space Xn is built with a greedy algorithm that is adapted to F in the sense that it is generated by elements of F itself. The algorithm also selects the linear functionals (σi)ni=1 from a dictionary Σ ⊂ X'. In this paper, we study the interpolation error maxf∊F ‖f - Jn[f]‖X by comparing it with the best possible performance on an n dimensional space, i.e., the Kolmogorov n-width of F in X, dn(F,X). For polynomial or exponential decay rates of dn(F,X), we prove that the interpolation error has the same behavior modulo the norm of the interpolation operator. Sharper results are obtained in the case where X is a Hilbert space. [ABSTRACT FROM AUTHOR]

We seek discrete approximations to solutions u : Ω → ℝ of semilinear elliptic PDE of the form Δu + fs (u) = 0, where fs is a one-parameter family of nonlinear functions and Ω is a domain in ℝd. The main achievement of this paper is the approximation of solutions to the PDE on the cube Ω = (0,π)³ ⊆ ℝ³. There are 323 possible isotropy subgroups of functions on the cube, which fall into 99 conjugacy classes. The bifurcations with symmetry in this problem are quite interesting, including many with 3-dimensional critical eigenspaces. Our automated symmetry analysis is necessary with so many isotropy subgroups and bifurcations among them, and it allows our code to follow one branch in each equivalence class that is created at a bifurcation point. Our most complicated result is the complete analysis of a degenerate bifurcation with a 6-dimensional critical eigenspace. This article extends our work in [Internat. J. Bifur. Chaos Appl. Sci. Engrg., 19 (2009), pp. 2531-2556], wherein we combined symmetry analysis with modified implementations of the gradient Newton-Galerkin algorithm (GNGA [J. M. Neuberger and J. W. Swift, Internat. J. Bifur. Chaos Appl. Sci. Engrg., 11 (2001), pp. 801-820]) to automatically generate bifurcation diagrams and solution graphics for small, discrete problems with large symmetry groups. The code described in the current paper is efficiently implemented in parallel, allowing us to investigate a relatively fine-mesh discretization of the cube. We use the methodology and corresponding library presented in our previous paper [Int. J. Parallel Program., 40 (2012), pp. 443-464]. [ABSTRACT FROM AUTHOR]

In this paper we derive a framework for multiscale approximation of elliptic problems on standard and mixed form. The method presented is based on a splitting into coarse and fine scales together with a systematic technique for approximation of the fine scale part, based on the solution of decoupled localized subgrid problems. The fine scale approximation is then used to modify the coarse scale equations. A key feature of the method is that symmetry in the bilinear form is preserved in the discrete system. Other key features are a posteriori error bounds and adaptive algorithms based on these bounds. The adaptive algorithms are used for automatic tuning of the method parameters. In the last part of the paper we present numerical examples where we apply the framework to a problem in oil reservoir simulation. [ABSTRACT FROM AUTHOR]

Let A ∈ ℂN x N be a nonsingular complex matrix and b and c be complex vectors of length N. The goal of this paper is to investigate approaches for efficient approximations of the bilinear form c*A-1b. Equivalently, we wish to approximate the scalar value c*x, where x solves the linear system Ax = b. Here the matrix A can be very large or its elements can be too costly to compute so that A is not explicitly available and it is used only in the form of the matrix-vector product. Therefore a direct method is not an option. For A Hermitian positive definite, b*A-1b can be efficiently approximated as a by-product of the conjugate-gradient iterations, which is mathematically equivalent to the matching moment approximations computed via the Gauss-Christoffel quadrature. In this paper we propose a new method using the biconjugate gradient iterations which is applicable to the general complex case. The proposed approach will be compared with existing ones using analytic arguments and numerical experiments. [ABSTRACT FROM AUTHOR]

In (SIAM J. Matrix Anal. Appl., 23 (2002), pp. 706–727, we developed numerical algorithms for computing sparse low-rank approximations of matrices, and we also provided a detailed error analysis of the proposed algorithms together with some numerical experiments. The low-rank approximations are constructed in a certain factored form with the degree of sparsity of the factors controlled by some user-specified parameters. In this paper, we cast the sparse low-rank approximation problem in the framework of penalized optimization problems. We discuss various approximation schemes for the penalized optimization problem which are more amenable to numerical computations. We also include some analysis to show the relations between the original optimization problem and the reduced one. We then develop a globally convergent discrete Newton-like iterative method for solving the approximate penalized optimization problems. We also compare the reconstruction errors of the sparse low-rank approximations computed by our new methods with those obtained using the methods in the earlier paper and several other existing methods for computing sparse low-rank approximations. Numerical examples show that the penalized methods are more robust and produce approximations with factors which have fewer columns and are sparser. [ABSTRACT FROM AUTHOR]

Max-plus methods have previously been used to solve deterministic control problems. The methods are based on max-plus (or min-plus) expansions and can yield curse-of-dimensionalityfree numerical methods. In this paper, we explore min-plus methods for continuous-time stochastic control on a finite-time horizon. We first approximate the original value function via timediscretization. By generalizing the min-plus distributive property to continuum spaces, we obtain an algorithm for recursive computation of the time-discretized values, which we refer to as the idempotent distributed dynamic programming principle (IDDPP). Under the IDDPP, the value function at each step can be represented as an infimum of functions in a certain class. This is a min-plus expansion for the value function. For the specific class of problems considered here, we see that the class can be taken as that consisting of the quadratic functions. A means for reducing the numbers of constituent quadratic functions is discussed. [ABSTRACT FROM AUTHOR]

This paper is on the construction of energy-minimizing coarse spaces that obey certain functional constraints and can thus be used, for example, to build robust coarse spaces for elliptic problems with large variations in the coefficients. In practice they are built by patching together solutions to appropriate local saddle point or eigenvalue problems. We develop an abstract framework for such constructions, akin to an abstract Bramble--Hilbert-type lemma, and then apply it in the design of coarse spaces for discretizations of PDEs with highly varying coefficients. The stability and approximation bounds of the constructed interpolant are in the weighted L2 norm and are independent of the variations in the coefficients. Such spaces can be used, for example, in two-level overlapping Schwarz algorithms for elliptic PDEs with large coefficient jumps generally not resolved by a standard coarse grid or for numerical upscaling purposes. Some numerical illustration is provided. [ABSTRACT FROM AUTHOR]

This paper investigates backscatter data for the inverse obstacle problem in impedance tomography, when the obstacles are small. It is shown that under this circumstance the backscatter data are close approximations of a rational function that has second or fourth order poles at the locations of the obstacles. Furthermore, a numerical method is presented to locate the obstacles via the poles of certain Laurent-Padé approximations. Numerical experiments explore the potential of this algorithm also for extended obstacles, taking into consideration that the problem is severely ill-posed. [ABSTRACT FROM AUTHOR]

A new algorithm is developed for computing etAB, where A is an n x n matrix and B is n x n0 with n0 « n. The algorithm works for any A, its computational cost is dominated by the formation of products of A with n x n0 matrices, and the only input parameter is a backward error tolerance. The algorithm can return a single matrix etA B or a sequence Due to image rights restrictions, multiple line equation(s) cannot be graphically displayed. on an equally spaced grid of points tk. It uses the scaling part of the scaling and squaring method together with a truncated Taylor series approximation to the exponential. It determines the amount of scaling and the Taylor degree, using the recent analysis of Al-Mohy and Higham [SIAM J. Matrix Anal. Appl., 31 (2009), pp. 970 989], which provides sharp truncation error bounds expressed in terms of the quantities ||Ak

In this paper we proposed quasi-Newton and limited memory quasi-Newton methods for objective functions defined ell Grassmannians or a product of Grassmannians. Specifically we defined BFGS and limited memory BFGS updates in local and global coordinates oil Grassmannians or a product, of these. We proved that, when local coordinates are used, our BFGS updates on Grassmaunians share the same optimality property as the usual BFGS updates on Euclidean spaces. When applied to the best multilinear rank approximation problem for general and symmetric tensors, our approach yields fast, robust, and accurate algorithms that exploit the special Grassmannian structure of the respective problems and which work on tensors of large dimensions and arbitrarily high order. Extensive numerical experiments are included to substantiate our claims. [ABSTRACT FROM AUTHOR]

In this paper we develop new methods for computing k-dimensional invariant manifolds of delayed systems for k ≥ 2. Our current implementation is built for k = 2 only, but the numerical and algorithmic challenges encountered in this case will be also present for any k > 1. For small delays, we consider methods for approximating delay differential equations (DDEs) with ordinary differential equations (ODEs). Once these approximations are made, any existing method for computing invariant manifolds of ODEs can then be used directly. We derive bounds on errors incurred by the most natural of these approximations. For large delays, we extend to DDEs the method originally introduced by Krauskopf and Osinga [Chaos, 9 (1999), pp. 768-774] for invariant manifolds of ODEs. We test the convergence of the resulting algorithms numerically and further illustrate our approach by computing two-dimensional unstable manifolds of equilibria in the context of phase-conjugate feedback lasers. [ABSTRACT FROM AUTHOR]

This paper shows how to compute O(√log n)-approximations to the Sparsest Cut and Balanced Separator problems in Õ(n²) time, thus improving upon the recent algorithm of Arora, Rao, and Vazirani [Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004, pp. 222-231]. Their algorithm uses semidefinite programming and requires Õ (n9.5) time. Our algorithm relies on efficiently finding expander flows in the graph and does not solve semidefinite programs. The existence of expander flows was also established by Arora, Rao, and Vazirani. [ABSTRACT FROM AUTHOR]

In Part II of this paper we first refine the analysis of error-free vector transformations presented in Part I. Based on that we present an algorithm for calculating the rounded-to-nearest result of s := Σ pi for a given vector of floating-point numbers pi, as well as algorithms for directed rounding. A special algorithm for computing the sign of s is given, also working for huge dimensions. Assume a floating-point working precision with relative rounding error unit eps. We define and investigate a K-fold faithful rounding of a real number r. Basically the result is stored in a vector Resν of K nonoverlapping floating-point numbers such that Σ Resν approximates r with relative accuracy epsK, and replacing ResK by its floating-point neighbors in Σ Resν forms a lower and upper bound for r. For a given vector of floating-point numbers with exact sum s, we present an algorithm for calculating a K-fold faithful rounding of s using solely the working precision. Furthermore, an algorithm for calculating a faithfully rounded result of the sum of a vector of huge dimension is presented. Our algorithms are fast in terms of measured computing time because they allow good instruction-level parallelism, they neither require special operations such as access to mantissa or exponent, they contain no branch in the inner loop, nor do they require some extra precision. The only operations used are standard floating-point addition, subtraction, and multiplication in one working precision, for example, double precision. Certain constants used in the algorithms are proved to be optimal. [ABSTRACT FROM AUTHOR]

This paper presents a new method for the numerical solution of nonlinear multiobjective optimization problems with an arbitrary partial ordering in the objective space induced by a closed pointed convex cone. This algorithm is based on the well-known scalarization approach by Pascoletti and Serafini and adaptively controls the scalarization parameters using new sensitivity results. The computed image points give a nearly equidistant approximation of the whole Pareto surface. The effectiveness of this new method is demonstrated with various test problems and an applied problem from medicine. [ABSTRACT FROM AUTHOR]

In this paper we study a discrete version of the classical team decision problem. It has been shown previously that the general discrete team decision problem is NP-hard. Here we present an efficient approximation algorithm for this problem. For the maximization version of this problem with nonnegative rewards, this algorithm computes decision rules which are guaranteed to be within a fixed bound of optimal. [ABSTRACT FROM AUTHOR]

We propose a new algebraic multigrid (AMG) method for solving the eddy current approximations to Maxwell's equations. This AMG method has its roots in an algorithm proposed by Reitzinger and Schöberl. The main focus in the Reitzinger and Schöberl method is to maintain null-space properties of the weak ∇ × ∇ × operator on coarse grids. While these null-space properties are critical, they are not enough to guarantee h-independent convergence rates of the overall multigrid scheme. We present a new strategy for choosing intergrid transfers that not only maintains the important null-space properties on coarse grids but also yields significantly improved multigrid convergence rates. This improvement is related to those we explored in a previous paper, but is fundamentally simpler, easier to compute, and performs better with respect to both multigrid operator complexity and convergence rates. The new strategy builds on ideas in smoothed aggregation to improve the approximation property of an existing interpolation operator. By carefully choosing the smoothing operators, we show how it is sometimes possible to achieve h-independent convergence rates with a modest increase in multigrid operator complexity. Though this ideal case is not always possible, the overall algorithm performs significantly better than the original scheme in both iterations and run time. Finally, the Reitzinger and Schöberl method, as well as our previous smoothed method, are shown to be special cases of this new algorithm. [ABSTRACT FROM AUTHOR]

In this paper we study a variational approach for filling in regions of missing data in two-dimensionaland three-dimensionaldigitalimages. Applications of this technique include the restoration of old photographs and removal of superimposed text like dates, subtitles, or publicity, or the zooming of images. The approach presented here, initially introduced in [IEEE Trans. Image Pr cess.,10 (2001), pp. 1200-1211] is based on a joint interpolation of the image gray levels and gradient/isophotes directions, smoothly extending the isophote lines into the holes of missing data. The process underlying this approach can be considered as an interpretation of the Gestaltist's principle of good continuation. We study the existence of minimizers of our functional and its approximation by minima of smoother functionals. Then we present the numerical algorithm used to minimize it and display some numerical experiments. [ABSTRACT FROM AUTHOR]

In this paper we consider a method of adapting Dubuc -Deslauriers subdivision, which is defined for bi-infinite sequences, to accommodate sequences of finite length. After deriving certain useful properties of the Dubuc -Deslauriers refinable function on R, we define a multiscale finite sequence of functions on a bounded interval, which are then proved to be refinable. Using this fact, the resulting adapted interpolatory subdivision scheme for finite sequences is then shown to be convergent. Corresponding interpolation wavelets on an interval are defined, and explicit formulations of the resulting decomposition and reconstruction algorithms are calculated. Finally, we give two numerical examples on signature smoothing and two-dimensional feature extraction of the subdivision and wavelet algorithms. [ABSTRACT FROM AUTHOR]

In this paper we show that the use of spectral Galerkin methods for the approximation of the Boltzmann equation in the velocity space permits one to obtain spectrally accurate numerical solutions at a reduced computational cost. We prove that the spectral algorithm preserves the total mass and approximates with infinite-order accuracy momentum and energy. Consistency of the method is also proved, and a stability result for a smoothed positive scheme is given. We demonstrate that the Fourier coefficients associated with the collision kernel of the equation have a very simple structure and in some cases can be computed explicitly. Numerical examples for homogeneous test problems in two and three dimensions confirm the advantages of the method. [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]