Search

Discontinuous Galerkin (DG) and mixed finite element (MFE) methods are two popular methods that possess local mass conservation. In this paper we investigate DG-DG and DG-MFE domain decomposition couplings using mortar finite elements to impose weak continuity of fluxes and pressures on the interface. The subdomain grids need not match, and the mortar grid may be much coarser, giving a two-scale method. Convergence results in terms of the fine subdomain scale h and the coarse mortar scale H are established for both types of couplings. In addition, a nonoverlapping parallel domain decomposition algorithm is developed, which reduces the coupled system to an interface mortar problem. The properties of the interface operator are analyzed. [ABSTRACT FROM AUTHOR]

In this paper we develop a posteriori error estimates for finite element discretization of elliptic optimization problems with pointwise inequality constraints on the control variable. We derive error estimators for assessing the discretization error with respect to the cost functional as well as with respect to a given quantity of interest. These error estimators provide quantitative information about the discretization error and guide an adaptive mesh refinement algorithm allowing for substantial saving in degrees of freedom. The behavior of the method is demonstrated on numerical examples. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the effects of pollution error on the performance of the parallel adaptive finite element technique proposed by Bank and Holst in 2000 [R. E. Bank and M. Holst, SIAM J. Sci. Comput., 22 (2000), pp. 1411-1443]. In particular, we consider whether the performance of the algorithm as it was originally proposed can be improved through the use of certain dual functions which give an indication of the global influences on subdomain errors. [ABSTRACT FROM AUTHOR]

We consider the problem of performing accurate computations with rectangular (m × n) totally nonnegative matrices. The matrices under consideration have the property of having a unique representation as products of nonnegative bidiagonal matrices. Given that representation, one can compute the inverse, LDU decomposition, eigenvalues, and SVD of a totally nonnegative matrix to high relative accuracy in O(max(m3, n3)) time-much more accurately than conventional algorithms that ignore that structure. The contribution of this paper is to show that the high relative accuracy is preserved by operations that preserve the total nonnegativity-taking a product, re-signed inverse (when m = n), converse, Schur complement, or submatrix of a totally nonnegative matrix, any of which costs at most O(max(m3, n3)). In other words, the class of totally nonnegative matrices for which we can do numerical linear algebra very accurately in O(max(m3, n3)) time (namely, those for which we have a product representation via nonnegative bidiagonals) is closed under the operations listed above. [ABSTRACT FROM AUTHOR]

We introduce a new approach to design parameterized algorithms on planar graphs which builds on the seminal results of Robertson and Seymour on graph minors. Graph minors provide a list of powerful theoretical results and tools. However, the widespread opinion in the graph algorithms community about this theory is that it is of mainly theoretical importance. In this paper we show how deep min-max and duality theorems from graph minors can be used to obtain exponential speed-up to many known practical algorithms for different domination problems. Our use of branch-width instead of the usual tree-width allows us to obtain much faster algorithms. By using this approach, we show that the k-dominating set problem on planar graphs can be solved in time O(215.13√k + n³). [ABSTRACT FROM AUTHOR]

A well-known generalization of Shannon's sampling theorem states that a bandlimited function can be reconstructed from its periodic nonuniformly spaced samples if the effective sampling rate is at least the Nyquist rate. Analogous to Shannon's sampling theorem this generalization requires that an infinite number of samples be available, which, however, is never the case in practice. Most existing reconstruction methods for periodic nonuniform sampling yield very low order (often not even first order) accuracy when only a finite number of samples is given. In this paper we propose a fast, numerically robust, root-exponential accurate reconstruction method. The efficiency and accuracy of the algorithm is obtained by fully exploiting the sampling structure and utilizing localized Fourier analysis. We discuss applications in analog-to-digital conversion where nonuniform periodic sampling arises in various situations. Finally, we demonstrate the performance of our algorithm by numerical examples. [ABSTRACT FROM AUTHOR]

One of the most interesting dynamical systems used in numerical analysis is the QR algorithm. An added maneuver to improve the convergence behavior is the QR iteration with shift which is of fundamental importance in eigenvalue computation. This paper is a theoretical study of the set of all isospectral matrices ‘reachable’ by the dynamics of the QR algorithm with shift. A matrix B is said to be reachable by A if B = RQ + μI, where A - μI = QR is the QR decomposition for some μ ϵ R. It is proved that in general the QR algorithm with shift is neither reflexive nor symmetric. Examples are given to demonstrate that this relation is neither transitive nor antisymmetric. It is further discovered that the reachable set from a given n x n matrix A forms 2n-1 disjoint open loops if n is even and 2n-2 disjoint components each of which is no longer a loop when n is odd. [ABSTRACT FROM AUTHOR]

We consider two-dimensional elliptic problems with discontinuous coefficients discretized by the finite element method on geometrically conforming nonmatching triangulations across the interface using the mortar technique. The resulting discrete problem is solved by a dual-primal FETI method. In this paper we introduce and analyze a preconditioner with a special scaling of coefficients and step parameters and establish convergence bounds. We show that the preconditioner is almost optimal with constants independent of the jumps of coefficients and step parameters. Extensive computational evidence is presented that illustrates an almost optimal convergence for a variety of situations (distribution of subregions, grid assignment, grid ratios, number of subregions) for both continuous and discontinuous problems. [ABSTRACT FROM AUTHOR]

Multigrid algorithms for Co interior penalty methods for fourth order elliptic boundary value problems on polygonal domains are studied in this paper. It is shown that V -cycle, F-cycle and W-cycle algorithms are contractions if the number of smoothing steps is sufficiently large. The contraction numbers of these algorithms are bounded by Cm-α, where m is the number of presmoothing (and postsmoothing) steps, α is the index of elliptic regularity, and the positive constant C is mesh-independent. These estimates are established for a smoothing scheme that uses a Poisson solve as a preconditioner, which can be easily implemented because the Co finite element spaces are standard spaces for second order problems. Furthermore the variable V -cycle algorithm is also shown to be an optimal preconditioner. [ABSTRACT FROM AUTHOR]

Centroidal Voronoi tessellations (CVTs) are Voronoi tessellations of a bounded geometric domain such that the generating points of the tessellations are also the centroids (mass centers) of the corresponding Voronoi regions with respect to a given density function. Centroidal Voronoi tessellations may also be defined in more abstract and more general settings. Due to the natural optimization properties enjoyed by CVTs, they have many applications in diverse fields. The Lloyd algorithm is one of the most popular iterative schemes for computing the CVTs but its theoretical analysis is far from complete. In this paper, some new analytical results on the local and global convergence of the Lloyd algorithm are presented. These results are derived through careful utilization of the optimization properties shared by CVTs. Numerical experiments are also provided to substantiate the theoretical analysis. [ABSTRACT FROM AUTHOR]

In this paper we study the stability for all positive time of the fully implicit Euler scheme for the two-dimensional Navier—Stokes equations. More precisely, we consider the time discretization scheme and with the aid of the discrete Gronwall lemma and the discrete uniform Gronwall lemma we prove that the numerical scheme is stable. [ABSTRACT FROM AUTHOR]

The goal of this paper is to reconstruct a collection of small inclusions inside a homogeneous object by applying a heat flux and measuring the induced temperature on its boundary. Taking advantage of the smallness of the inclusions, we design efficient noniterative algorithms for locating the inclusions from boundary measurements of the temperature. We illustrate the feasibility and the viability of our algorithms by numerical examples. [ABSTRACT FROM AUTHOR]

This paper proves the stability of a variant of Gragg's unitary Hessenberg QR algorithm (UHQR). It is shown that a single UHQR iteration with numerically unimodular shift applied to the Schur parameters and complementary parameters of a unitary Hessenberg matrix H gives computed parameters for QHHQ that are close to those obtained from a perturbed set of parameters using a perturbed shift with no numerical error. The perturbations of the parameters and the shift are bounded. [ABSTRACT FROM AUTHOR]

Algebraic multigrid (AMG) is a very efficient iterative solver and preconditioner for large unstructured sparse linear systems. Traditional coarsening schemes for AMG can, however, lead to computational complexity growth as problem size increases, resulting in increased memory use and execution time, and diminished scalability. Two new parallel AMG coarsening schemes are proposed that are based solely on enforcing a maximum independent set property, resulting in sparser coarse grids. The new coarsening techniques remedy memory and execution time complexity growth for various large three-dimensional (3D) problems. If used within AMG as a preconditioner for Krylov subspace methods, the resulting iterative methods tend to converge fast. This paper discusses complexity issues that can arise in AMG, describes the new coarsening schemes, and examines the performance of the new preconditioners for various large 3D problems. [ABSTRACT FROM AUTHOR]

In this paper we present optimization algorithms for image restoration based on the total variation (TV) minimization framework of Rudin, Osher, and Fatemi (ROF). Our approach formulates TV minimization as a second-order cone program which is then solved by interior-point algorithms that are efficient both in practice (using nested dissection and domain decomposition) and in theory (i.e., they obtain solutions in polynomial time). In addition to the original ROF minimization model, we show how to apply our approach to other TV models, including ones that are not solvable by PDE-based methods. Numerical results on a varied set of images are presented to illustrate the effectiveness of our approach. [ABSTRACT FROM AUTHOR]

In this paper two noniterative algorithms for locating small electromagnetic inclusions from the scattering amplitude at a fixed frequency are developed. In particular, a variety of numerical results is presented to highlight their potential and their limitations. [ABSTRACT FROM AUTHOR]

This paper is concerned with the solution of a linear system with multiple right-hand sides. Such problems arise from nonlinear, time-dependent, inverse, or optimization problems. In order to solve these problems efficiently we use block variants of the conjugate gradient method and combine them with cache aware algorithms. Further, we describe the acceleration of algebraic multigrid (AMG) methods by using such cache aware algorithms. Finally, numerical studies are presented that show the high efficiency of the proposed methods. [ABSTRACT FROM AUTHOR]

In this paper, we present new algorithms that can replace the diagonal entries of a Hermitian matrix by any set of diagonal entries that majorize the original set without altering the eigenvalues of the matrix. They perform this feat by applying a sequence of (N-1) or fewer plane rotations, where N is the dimension of the matrix. Both the Bendel--Mickey and the Chan--Li algorithms are special cases of the proposed procedures. Using the fact that a positive semidefinite matrix can always be factored as $\mtx{X^\adj X}$, we also provide more efficient versions of the algorithms that can directly construct factors with specified singular values and column norms. We conclude with some open problems related to the construction of Hermitian matrices with joint diagonal and spectral properties. [ABSTRACT FROM AUTHOR]

Higher order panel methods are used to solve the Laplace equation in the presence of complex geometries. These methods are useful when globally accurate velocity or potential fields are desired as in the case of vortex based fluid flow solvers. This paper develops a fast multipole algorithm to compute velocity fields due to higher order, two-dimensional vortex panels. The technique is applied to panels having a cubic geometry and a linear distribution of vorticity. The results of the present method are compared with other available techniques. [ABSTRACT FROM AUTHOR]

In this work we study a dynamical system with a complicated nonlinearity, which describes oscillation of a turbine rotor, and give an algorithm to compute Melnikov functions for analysis of its chaotic behavior. We first derive the rotor model whose nonlinear term brings difficulties to investigating the distribution and qualitative properties of its equilibria. This nonlinear model provides a typical example of a system for which the homoclinic and heteroclinic orbits cannot be analytically determined. In order to apply Melnikov's method to make clear the underlying conditions for chaotic motion, we present a generic algorithm that provides a systematic procedure to compute Melnikov functions numerically. Substantial analysis is done so that the numerical approximation precision at each phase of the computation can be guaranteed. Using the algorithm developed in this paper, it is straightforward to obtain a sufficient condition for chaotic motion under damping and periodic external excitation, whenever the rotor parameters are given. [ABSTRACT FROM AUTHOR]

Recently, D. Corneil found a simple 3-sweep lexicographic breadth first search (LexBFS) algorithm for the recognition of proper interval graphs. We point out how to modify Corneil's algorithm to make it a certifying algorithm, and then describe a similar certifying 3-sweep LexBFS algorithm for the recognition of proper interval bigraphs. It follows from an earlier paper that the class of proper interval bigraphs is equal to the better known class of bipartite permutation graphs, and so we have a certifying algorithm for that class as well. All our algorithms run in time O(m+n), including the certification phase. The certificates of representability (the intervals) can be authenticated in time O(m + n). The certificates of nonrepresentability (the forbidden subgraphs) can be authenticated in time O(n). [ABSTRACT FROM AUTHOR]

Parameterization of unstructured surface meshes is of fundamental importance in many applications of digital geometry processing. Such parameterization approaches give rise to large and exceedingly ill-conditioned systems which are difficult or impossible to solve without the use of sophisticated multilevel preconditioning strategies. Since the underlying meshes are very fine to begin with, such multilevel preconditioners require mesh coarsening to build an appropriate hierarchy. In this paper we consider several strategies for the construction of hierarchies using ideas from mesh simplification algorithms used in the computer graphics literature. We introduce two novel hierarchy construction schemes and demonstrate their superior performance when used in conjunction with a multigrid preconditioner. [ABSTRACT FROM AUTHOR]

We present an algorithm to compute the one-dimensional stable manifold of a saddle point for a planar map. In contrast to current standard techniques, here it is not necessary to know the inverse or approximate it, for example, by using Newton's method. Rather than using the inverse, the manifold is grown starting from the linear eigenspace near the saddle point by adding a point that maps back onto an earlier segment of the stable manifold. The performance of the algorithm is compared to other methods using an example in which the inverse map is known explicitly. The strength of our method is illustrated with examples of noninvertible maps, where the stable set may consist of many different pieces, and with a piecewise-smooth model of an interrupted cutting process. The algorithm has been implemented for use in the DsTool environment and is available for download with this paper. [ABSTRACT FROM AUTHOR]

We present and study a nonconforming domain decomposition method for the discretization of the three-dimensional Stokes problem in the velocity-pressure formulation. The approximation is based on some local mixed finite elements for nonmatching tetrahedral grids. The aim pursued is a systematic construction of the mortared discrete velocity space, the pressure being not subjected to any matching constraints across the interfaces. Using the bubble stabilization techniques, applied in Brezzi and Marini's paper to the three fields method [Math. Cornp., 70 (2001), pp. 911-934], allows us to define an algorithm which is easy to implement. The numerical analysis relies on the pressure-splitting argument of Boland and Nicolaides and allows us to establish an inf-sup condition with a constant that does not depend on the mesh size or on the total number of the subdomains. Then, by the Berger-Scott-Strang lemma written down for our saddle point system we derive optimal accuracy results. [ABSTRACT FROM AUTHOR]

Accurate numerical modeling of complex physical, chemical, and biological systems requires numerical simulation capability over a large range of length scales, with the ability to capture rapidly varying phenomena localized in space and/or time. Adaptive mesh refinement (AMR) is a numerical process for dynamically introducing local fine resolution on computational grids during the solution process, in response to unresolved error in a computation. Fast adaptive composite-grid (FAC) methods are a class of algorithms that exploit the multilevel structure of AMR grids to solve elliptic problems efficiently. This paper develops a theoretical foundation for AFACx, an asynchronous FAC method. A new multilevel condition number estimate establishes that the convergence rate of the AFACx algorithm does not degrade as the number of refinement levels in the AMR hierarchy increases. [ABSTRACT FROM AUTHOR]

This paper analyzes asymptotic convergence properties of policy iteration in a class of stationary, infinite-horizon Markovian decision problems that arise in optimal growth theory. These problems have continuous state and control variables and must therefore be discretized in order to compute an approximate solution. The discretization may render inapplicable known convergence results for policy iteration such as those of Puterman and Brumelle [Math. Oper. Res., 4 (1979), pp. 60-69]. Under certain regularity conditions, we prove that for piecewise linear interpolation, policy iteration converges quadratically. Also, under more general conditions we establish that convergence is superlinear. We show how the constants involved in these convergence orders depend on the grid size of the discretization. These theoretical results are illustrated with numerical experiments that compare the performance of policy iteration and the method of successive approximations. [ABSTRACT FROM AUTHOR]

Finding approximate solutions to systems of it nonlinear equations in it real variables is a much studied problem in numerical analysis. Somewhat more recently, researchers have developed numerical methods to provide mathematically rigorous error bounds on such solutions. (We say that we "verify" existence of the solution within those bounds on the variables.) However, when the Jacobi matrix is singular at the solution, no computational techniques to verify existence can handle the general case. Nonetheless, computational verification that one or more solutions exists within a region in complex space containing the real bounds is possible by computing the topological degree. In a previous paper, we presented theory and algorithms for the simplest case, when the rank-defect of the Jacobian matrix at the solution is 1 and the topological index is 2. Here, we generalize that result to arbitrary topological index d ≥ 2: We present theory, algorithms, and experimental results. We also present a heuristic for determining the degree, obtaining a value that we can subsequently verify with our algorithms. Although execution times are slow compared to corresponding bound verification processes for nonsingular systems, the order with respect to system size is still cubic. [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 propose a nonoverlapping domain decomposition method for solving the three-dimensional Maxwell equations, based on the edge element discretization. For the Schur complement system on the interface, we construct an efficient preconditioner by introducing two special coarse subspaces defined on the nonoverlapping sub domains. It is shown that the condition number of the preconditioned system grows only polylogarithmically with the ratio between the subdomain diameter and the finite element mesh size but possibly depends on the jumps of the coefficients. [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]

We study some continuous dynamical systems associated with constrained optimization problems. For that purpose, we introduce the concept of elliptic barrier operators and develop a unified framework to derive and analyze the associated class of gradient-like dynamical systems, called A-driven descent method (A-DM). Prominent methods belonging to this class include several continuous descent methods studied earlier in the literature such as steepest descent method, continuous gradient projection methods and Newton-type methods as well as continuous interior descent methods such as Lotka-Volterra-type differential equations and Riemannian gradient methods. Related discrete iterative methods such as proximal interior point algorithms based on Bregman functions and second order homogeneous kernels can also be recovered within our framework and allow for deriving some new and interesting dynamics. We prove global existence and strong viability results of the corresponding trajectories of (A-DM) for a smooth objective function. When the objective function is convex, we analyze the asymptotic behavior at infinity of the trajectory produced by the proposed class of dynamical systems (A -DM). In particular, we derive a general criterion ensuring the global convergence of the trajectory of (A-DM) to a minimizer of a convex function over a closed convex set. This result is then applied to several dynamics built upon specific elliptic barrier operators. Throughout the paper, our results are illustrated with many examples. [ABSTRACT FROM AUTHOR]

In this paper we investigate the accuracy of two numerical procedures commonly used to solve 2D advection problems: spectral and finite difference (FD) schemes. These schemes are widely used, simulating, e.g., neutral and plasma flows. FD schemes have long been considered fast, relatively easy to implement, and applicable to complex geometries, but are somewhat inferior in accuracy compared to spectral schemes. Using two study cases at high Reynolds number, the merging of two equally signed Gaussian vortices in a periodic box and dipole interaction with a no-slip wall, we will demonstrate that the accuracy of FD schemes can be significantly improved if one is careful in choosing an appropriate FD scheme that reflects conservation properties of the nonlinear terms and in setting up the grid in accordance with the problem. [ABSTRACT FROM AUTHOR]

In the convergence theory of multisplittings for symmetric positive definite (s.p.d.) matrices it is usually assumed that the weighting matrices are scalar matrices, i.e., multiples of the identity. In this paper, this restrictive condition is eliminated. In its place it is assumed that more than one (inner) iteration is performed in each processor (or block). The theory developed here is applied to nonstationary multisplittings for s.p.d. matrices, as well as to two-stage multisplittings for symmetric positive semidefinite matrices. [ABSTRACT FROM AUTHOR]

In this paper, we study some efficient numerical methods for parameter identifications in elliptic systems. The proposed numerical methods are conducted iteratively and each iteration involves only solving positive definite linear algebraic systems, although the original inverse problems are ill-posed and highly nonlinear. The positive definite systems can be naturally preconditioned with their corresponding block diagonal matrices. Numerical experiments are presented to illustrate the efficiency of the proposed algorithms. [ABSTRACT FROM AUTHOR]

This paper presents the results of a scalability study for a three-dimensional semi- coarsening multigrid solver on a distributed memory computer. In particular, we are interested in the scalability of the solver-how the solution time varies as both problem size and number of processors are increased. For an iterative linear solver, scalability involves both algorithmic issues and implementation issues. We examine the scalability of the solver theoretically by constructing a simple parallel model and experimentally by results obtained on an IBM SP. The results are compared with those obtained for other solvers on the same computer. [ABSTRACT FROM AUTHOR]

This paper formulates several algorithms for the direct computation of periodic orbits as solutions of boundary value problems. The algorithms emphasize the use of coarse meshes and high orders of accuracy. Convergence theorems are given in the limit of increasing order with a fixed mesh. The algorithms are implemented with the use of MATLAB and ADOL-C, a software package for automatic differentiation. Automatic differentiation enables accurate computation of high-order derivatives of functions without the truncation errors inherent in finite difference calculations. We embed the algorithms in a continuation framework and extend them to compute saddle-node bifur- cations of periodic orbits directly. We present data from numerical studies of four test problems, making some comparisons with other methods for computing periodic orbits. These results demonstrate that high-order methods based upon automatic differentiation are capable of high precision with small meshes. [ABSTRACT FROM AUTHOR]

A successive continuation method for locating connecting orbits in parametrized systems of autonomous ODEs was considered in [Numer. Algorithms, 14 (1997), pp. 103­124]. In this paper we present an improved algorithm for locating and continuing connecting orbits, which includes a new algorithm for the continuation of invariant subspaces. The latter algorithm is of independent interest and can be used in contexts different than the present one. [ABSTRACT FROM AUTHOR]

Low-rank approximation of large and/or sparse matrices is important in many applications, and the singular value decomposition (SVD) gives the best low-rank approximations with respect to unitarily-invariant norms. In this paper we show that good low-rank approximations can be directly obtained from the Lanczos bidiagonalization process applied to the given matrix without computing any SVD. We also demonstrate that a so-called one-sided reorthogonalization process can be used to maintain an adequate level of orthogonality among the Lanczos vectors and produce accurate low-rank approximations. This technique reduces the computational cost of the Lanczos bidiagonalization process. We illustrate the efficiency and applicability of our algorithm using numerical examples from several applications areas. [ABSTRACT FROM AUTHOR]

Various forms of sparse approximate inverses (SAI) have been shown to be useful for preconditioning. Their potential usefulness in a parallel environment has motivated much interest in recent years. However, the capability of an approximate inverse in eliminating the local error has not yet been fully exploited in multigrid algorithms. A careful examination of the iteration matrices of these approximate inverses indicates their superiority in smoothing the high-frequency error in addition to their inherent parallelism. We propose a new class of SAI smoothers in this paper and present their analytic smoothing factors for constant coefficient PDEs. The following are several distinctive features that make this technique special: By adjusting the quality of the approximate inverse, the smoothing factor can be improved accordingly. For hard problems, this is useful. In contrast to the ordering sensitivity of other smoothing techniques, this technique is ordering independent. In general, the sequential performance of many superior parallel algorithms is not very competitive. This technique is useful in both parallel and sequential computations. Our theoretical and numerical results have demonstrated the effectiveness of this new technique. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to derive new computable convergence bounds for GMRES. The new bounds depend on the initial guess and are thus conceptually different from standard “worst-case” bounds. Most importantly, approximations to the new bounds can be computed from information generated during the run of a certain GMRES implementation. The approximations allow predictions of how the algorithm will perform. Heuristics for such predictions are given. Numerical experiments illustrate the behavior of the new bounds as well as the use of the heuristics. [ABSTRACT FROM AUTHOR]

We develop an Eulerian­Lagrangian localized adjoint method (ELLAM) to solve two-dimensional advection-diffusion equations with all combinations of inflow and outflow Dirichlet, Neumann, and flux boundary conditions. The ELLAM formalism provides a systematic framework for implementation of general boundary conditions, leading to mass-conservative numerical schemes. The computational advantages of the ELLAM approximation have been demonstrated for a number of one-dimensional transport systems; practical implementations of ELLAM schemes in multiple spatial dimensions that require careful algorithm development are discussed in detail in this paper. Extensive numerical results are presented to compare the ELLAM scheme with many widely used numerical methods and to demonstrate the strength of the ELLAM scheme.

This paper describes surface evolution formulated in terms of a Hamilton­Jacobi equation and a solution algorithm based on a three-dimensional front tracking algorithm. Our method achieves sharp resolution in the evolution of surface edges and corners. This study is motivated by semiconductor chip evolution during deposition and resputtering processes. For this reason, we discuss here the effects of diffuse rescattering on surface features. We illustrate some of the three-dimensional capabilities of the front tracking algorithm. We also present a validation study by display of two-dimensional cross sections of three-dimensional simulations of a finite-length trench. The cross sections correspond to two-dimensional simulations of S. Hamaguchi and S. M. Rossnagel [J. Vac. Sci. Technol. B, 13 (1995), pp. 183–191].

In this paper a recently proposed additive version of the algebraic multilevel iteration method for iterative solution of elliptic boundary value problems is studied. The method constructs a nearly optimal order parameter-free preconditioner, which is robust with respect to anisotropy and discontinuity of the problem coefficients. It uses a new strategy for approximating the blocks corresponding to ‘new’ basis functions on each discretization level. To cope with the difficulties arising from the anisotropy, the problem on the coarsest mesh is solved using a bordering technique with a special choice of bordering vectors. The aim is to find a parameter-free ‘black-box’ robust solver. The results are derived in the framework of a hierarchical basis, linear finite element discretization of an elliptic problem on arbitrary triangular meshes, and a hierarchical basis, bilinear finite element discretization on Cartesian meshes. A comparison of the method with some other iterative solution techniques is presented. Robustness and high efficiency of the proposed algorithm are demonstrated on several model-type problems.

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]

The aim of this paper is to describe a variational spectral solver of the three dimensional operator (I + curl curl) which we often encounter when dealing with the Maxwell problem. We carry out a mathematical study proving the optimality of such an algorithm and we make an analysis of its complexity showing its efficiency. Finally, some applications to time-dependent partial differential equations obtained from the Maxwell model are presented. [ABSTRACT FROM AUTHOR]

The restarted GMRES algorithm proposed by Saad and Schultz [SIAM J. Sci. Statist. Comput., 7 (1986), pp. 856-869] is one of the most popular iterative methods for the solution of large linear systems of equations Ax = b with a nonsymmetric and sparse matrix. This algorithm is particularly attractive when a good preconditioner is available. The present paper describes two new methods for determining preconditioners from spectral information gathered by the Arnoldi process during iterations by the restarted GMRES algorithm. These methods seek to determine an invariant subspace of the matrix A associated with eigenvalues close to the origin and to move these eigenvalues so that a higher rate of convergence of the iterative methods is achieved. [ABSTRACT FROM AUTHOR]

In this paper we examine problems motivated by on-line financial problems and stochastic games. In particular, we consider a sequence of entirely arbitrary distinct values arriving in random order, and must devise strategies for selecting low values followed by high values in such a way as to maximize the expected gain in rank from low values to high values. First, we consider a scenario in which only one low value and one high value may be selected. We give an optimal on-line algorithm for this scenario, and analyze it to show that, surprisingly, the expected gain is n - O(1), and so differs from the best possible off-line gain by only a constant additive term (which is, in fact, fairly small—at most 15). In a second scenario, we allow multiple nonoverlapping low/high selections, where the total gain for our algorithm is the sum of the individual pair gains. We also give an optimal on-line algorithm for this problem, where the expected gain is n²/8 - Θ(n log n). An analysis shows that the optimal expected off-line gain is n²/6 + Θ(1), so the performance of our on-line algorithm is within a factor of 3/4 of the best off-line strategy. [ABSTRACT FROM AUTHOR]

The mortar methods are based on domain decomposition and they allow for the coupling of different variational approximations in different subdomains. The resulting methods are nonconforming but still yield optimal approximations. In this paper, we will discuss iterative substructuring algorithms for the algebraic systems arising from the discretization of symmetric, second-order, elliptic equations in two dimensions. Both spectral and finite element methods, for geometrically conforming as well as nonconforming domain decompositions, are studied. In each case, we obtain a polylogarithmic bound on the condition number of the preconditioned matrix. [ABSTRACT FROM AUTHOR]

The BR algorithm, a new method for calculating the eigenvalues of an upper Hes- senberg matrix, is introduced. It is a bulge-chasing algorithm like the QR algorithm, but, unlike the QR algorithm, it is well adapted to computing the eigenvalues of the narrow-band, nearly tridiagonal matrices generated by the look-ahead Lanczos process. This paper describes the BR algorithm and gives numerical evidence that it works well in conjunction with the Lanczos process. On the biggest problems run so far, the BR algorithm beats the QR algorithm by a factor of 30–60 in computing time and a factor of over 100 in matrix storage space. [ABSTRACT FROM AUTHOR]

In this paper, we study the additive Schwarz method for the h-p version of the finite element method in three dimensions. The main idea is to treat separately the h-version (linear) components and the p-version (high-order) components by a vertex-based method. It can also be viewed as a three-level method with the level being the linear finite element approximation on the coarse mesh, the linear finite element approximation on the fine mesh, and the high-order finite element approximation on the fine mesh, respectively. The resulting algorithm can be implemented in parallel on the subdomain level for the h-version components and on the element level for the p-version components. The condition number is of order [This symbol cannot be presented in ASCII format](1 + ln Hipi/hi)⇔2, where Hi stands for the diameter of the subdomain Ωi, hi is the diameter of the elements in Ωi, and pi is the maximum of the polynomial degrees used in Ωi. [ABSTRACT FROM AUTHOR]