Search

This paper is concerned with the convergence properties of iterative algorithms of conjugate gradient type applied to the computation of an extreme eigenvalue of a Hermitian operator via the optimization of the Rayleigh quotient functional. The algorithms in focus employ the line search for the extremum of the Rayleigh quotient functional in the direction that is a linear combination of the gradient and the previous search direction. An asymptotically explicit equation for the reduction in the eigenvalue error after the line search step as a function of the search direction is derived and applied to the analysis of the local convergence properties (i.e., the error reduction after an iteration) of the algorithms in question. The local (stepwise) asymptotic equivalence of various conjugate gradient algorithms and the generalized Davidson method is proved, and a new convergence estimate for conjugate gradient iterations is derived, showing the reduction in the eigenvalue error after any two consecutive iterations. The paper's analysis extensively employs remarkable properties of the operator of the so-called Jacobi orthogonal complement correction equation. [ABSTRACT FROM AUTHOR]

The paper concerns numerical algorithms for solving the Beltrami equation fz¯(z) = μ(z)fz(z) for a compactly supported μ. First, we study an efficient algorithm that has been proposed in [P. Daripa, J. Comput. Phys., 106 (1993), pp. 355-365] and [P. Daripa and D. Mashat, Numer. Algorithms, 18 (1998), pp. 133-157] and present its rigorous justification. We then propose a different scheme for solving the Beltrami equation which has a comparable speed and accuracy, but has the virtue of easier implementation by avoiding the use of the Hilbert transform. The present paper can also be viewed as a prologue to one important application of the Beltrami equation: it provides a detailed description of the algorithm that has been used in [D. Gaidashev, Nonlinearity, 20 (1998), pp. 713-741] and [D. Gaidashev and M. Yampolsky, Experiment. Math., 16 (2007), pp. 215-226] to address an important issue in complex dynamics-conjectural universality for Siegel disks. [ABSTRACT FROM AUTHOR]

The Lloyd algorithm originated in the context of optimal quantization and represents a fixed point iteration for computing an optimal quantizer. Reducing average distortion at every step, it constructs a Voronoi partition of the domain and replaces each generator with the centroid of the corresponding Voronoi cell. Optimal quantization is obtained in the case of a centroidal Voronoi tessellation (CVT), which is a special Voronoi tessellation of a domain Ω ϵ ℝd having the property that the generators of the Voronoi diagram are also the centers of mass, with respect to a given density function ? ⩾ 0, of the corresponding Voronoi cells. The Lloyd iteration is currently the most popular and elegant algorithm for computing CVTs and optimal quantizers, but many questions remain about its convergence, especially in d-dimensional spaces (d > 1). In this paper, we prove that any limit point of the Lloyd iteration in any dimensional spaces is nondegenerate provided that Ω is a convex and bounded set and ? belongs to L¹(Ω) and is positive almost everywhere. This ensures that the fixed point map remains closed and hence the standard theory of descent methods guarantees weak global convergence of the Lloyd iteration to the set of nondegenerate fixed point quantizers. While previously only conjectured, the convergence properties of the Lloyd iteration are rigorously justified under such minimal regularity assumptions on the density functional. The results presented in this paper go beyond existing convergence theories for CVTs and optimal quantization related algorithms and should be of interest to both the mathematical and engineering communities. [ABSTRACT FROM AUTHOR]

This paper is concerned with the development of well-balanced high order numerical schemes for systems of balance laws with a linear flux function, whose coefficients may be variable. First, well-balanced first order numerical schemes are obtained based on the use of exact solvers of Riemann problems that include both the flux and the source terms. Godunov's methods so obtained are extended to higher order schemes by using a technique of reconstruction of states. The main contribution of this paper is to introduce a reconstruction technique that preserves the well-balanced property of Godunov's methods. Some numerical experiments are presented to verify in practice the properties of the developed numerical schemes. [ABSTRACT FROM AUTHOR]

In this paper we consider the numerical solution of discrete boundary integral equations on polyhedral surfaces in three dimensions. When the solution contains typical edge singularities, highly stretched meshes are preferred to uniform meshes, since they reduce the number of degrees of freedom needed to obtain a fixed accuracy. The classical panel-clustering method can still be applied in the presence of such highly stretched meshes. However, we will show that the savings in computation time and storage become suboptimal because the nearfield matrix arising in the panel-clustering algorithm is no longer as sparse as it is in the case of uniform meshes. Hence, a natural question arises as to whether a new enhanced panel-clustering algorithm can be designed which performs efficiently even in the presence of highly stretched meshes. The main result of this paper is to formulate such an enhanced version of the panel-clustering algorithm. The key features of the algorithm are (i) the employment of partial analytic integration in the direction of stretching, yielding a new kernel function on a one-dimensional manifold where the influence of high aspect ratios in the stretched elements is removed, and (ii) the introduction of a generalized admissibility condition with respect to the partially integrated kernel, which ensures that certain stretched clusters which are inadmissible in the classical sense now become admissible. In the context of a model problem, we prove that our algorithm yields an accurate (up to the discretization error) matrix-vector multiplication which requires ...(NlogκN) operations, where N is the number of degrees of freedom and k is small and independent of the aspect ratio. The generalized admissibility condition can be viewed as an addition to the classical method which may be useful in general when stretched meshes are present. We also have performed a numerical experiment which shows that the sparsity of the nearfield matrix for the enhanced panel-clustering method is not negatively affected by stretched elements, and the method will perform optimally. [ABSTRACT FROM AUTHOR]

In this paper, an efficient and stable numerical algorithm for computing multiple saddle points with symmetries is developed by modifying the local minimax method established in [Y. Li and J. Zhou, SIAM J. Sci. Comput. 23 (2001), pp. 840--865; Y. Li and J. Zhou, SIAM J. Sci. Comput., 24 (2002), pp. 840--865]. First an invariant space is defined in a more general sense and a principle of invariant criticality is proved for the generalization. Then the orthogonal projection to the invariant space is used to preserve the invariance and to reduce computational error across iterations. Simple averaging formulas are used for the orthogonal projections. Numerical computations of examples with various symmetries, of which some can and others cannot be characterized by a compact group of linear isomorphisms, are carried out to confirm the theory and to illustrate applications. The mathematical features of various problems demonstrated in these examples fall into two categories: nodal solutions of saddle-point type with large Morse indices and nonradial positive solutions via symmetry breaking in radially symmetric elliptic problems. The new numerical algorithm generates these rather unstable solutions in an efficient and stable way. The existence of many unstable solutions and their behavior found in this paper remain to be investigated. [ABSTRACT FROM AUTHOR]

Local mesh-refining algorithms known from adaptive finite element methods are adopted for locally conservative and monotone finite volume discretizations of boundary value problems for steady-state convection-diffusion-reaction equations. The paper establishes residual-type explicit error estimators and averaging techniques for a posteriori finite volume error control with and without upwind in global H1- and L2-norms. Reliability and efficiency are verified theoretically and confirmed empirically with experimental support for the superiority of the suggested adaptive mesh-refining algorithms over uniform mesh refining. A discussion of adaptive computations in the simulation of contaminant concentration in a nonhomogeneous water reservoir concludes the paper. [ABSTRACT FROM AUTHOR]

A new fully variational approach is studied for elliptic grid generation (EGG). It is based on a general algorithm developed in a companion paper [A. L. Codd, T. A. Manteuffel, and S. F. McCormick, SIAM I Numer. Anal., 41 (2003), pp. 2197-2209] that involves using Newton's method to linearize an appropriate equivalent first-order system, first-order system least squares (FOSLS) to formulate and discretize the Newton step, and algebraic multigrid (AMG) to solve the resulting matrix equation. The approach is coupled with nested iteration to provide an accurate initial guess for finer levels using coarse-level computation. The present paper verifies the assumptions of the companion work and confirms the overall efficiency of the scheme with numerical experiments. [ABSTRACT FROM AUTHOR]

This paper discusses convergence behavior of the nonlinear inexact Uzawa algorithm for solving saddle-point problems presented in a recent paper of Bramble, Pasciak, and Vassilev (SIAM J. Numer. Anal., 34 (1997), pp. 1072­1092). It is shown that this algorithm converges under a condition weaker than that stated in their paper. Key words: saddle-point problems; nonlinear inexact Uzawa algorithm; convergence behavior [ABSTRACT FROM AUTHOR]

We study a block triangular preconditioner for finite element approximations of the linearized Navier-Stokes equations. The preconditioner is based on the augmented Lagrangian formulation of the problem and was introduced by the authors in [SIAM J. Sci. Comput., 28 (2006), pp. 2095-2113]. In this paper we prove field-of-values type estimates for the preconditioned system which lead to optimal convergence bounds for the GMRES algorithm applied to solve the system. Two variants of the preconditioner are considered: an ideal one based on exact solves for the velocity submatrix, and a more practical variant based on block triangular approximations of the velocity submatrix. [ABSTRACT FROM AUTHOR]

In this paper we develop boundary value methods for detecting Sacker-Sell spectra in discrete time dynamical systems. The algorithms are advancements of earlier methods for computing projectors of exponential dichotomies. The first method is based on the projector residual P² - P. If this residual is large, then the difference equation has no exponential dichotomy. Further criterions for detecting Sacker-Sell spectral intervals are the norm of end points and midpoints of the solution of a specific boundary value problem. Refined error estimates for the underlying approximation process are given, and the resulting algorithms are applied to an example with known continuous Sacker-Sell spectrum, as well as to the variational equation along orbits of Hénon's map. [ABSTRACT FROM AUTHOR]

The global macroscopic behavior of a dynamical system is encoded in the eigenfunctions of the associated Frobenius-Perron operator. For systems with low dimensional long term dynamics, efficient techniques exist for a numerical approximation of the most important eigenfunctions; cf. [M. Dellnitz and O. Junge, SIAM J. Numer. Anal., 36 (1999), pp. 491-515]. They are based on a projection of the operator onto a space of piecewise constant functions supported on a neighborhood of the attractor—Ulam's method. In this paper we develop a numerical technique which makes Ulam's approach applicable to systems with higher dimensional long term dynamics. It is based on ideas for the treatment of higher dimensional partial differential equations using sparse grids [C. Zenger, Sparse grids, in Parallel Algorithms for Partial Differential Equations (Kiel, 1990), Vieweg, Braunschweig, 1991, pp. 241-251; H.-J. Bungartz and M. Griebel, Acta Numer., 13 (2004), pp. 147-269]. Here, we use a sparse Haar tensor basis as the underlying approximation space. We develop the technique, establish statements about its complexity and convergence, and present two numerical examples. [ABSTRACT FROM AUTHOR]

This paper is concerned with the numerical minimization of energy functionals in Hilbert spaces involving convex constraints coinciding with a seminorm for a subspace. The optimization is realized by alternating minimizations of the functional on a sequence of orthogonal subspaces. On each subspace an iterative proximity-map algorithm is implemented via oblique thresholding, which is the main new tool introduced in this work. We provide convergence conditions for the algorithm in order to compute minimizers of the target energy. Analogous results are derived for a parallel variant of the algorithm. Applications are presented in domain decomposition methods for degenerate elliptic PDEs arising in total variation minimization and in accelerated sparse recovery algorithms based on l1-minimization. We include numerical examples which show efficient solutions to classical problems in signal and image processing. [ABSTRACT FROM AUTHOR]

In [Carlini, Falcone, Forcadel, and Monneau, SIAM J. Numer. Anal., 46 (2008), pp. 2920-2952], the authors have proposed a generalization of the classical fast marching method of Sethian for the eikonal equation in the case where the normal velocity depends on space and time and can change sign. The goal of this paper is to propose a modified version of the generalized fast marching method proposed in [Carlini, Falcone, Forcadel, and Monneau, SIAM J. Numer. Anal., 46 (2008), pp. 2920-2952] for which we state a general comparison principle. We also prove the convergence of the new algorithm. [ABSTRACT FROM AUTHOR]

In this paper, a new space-time discretization is proposed which is based on a modified mass matrix. The mass associated with a surface layer of elements is redistributed such that the inertia at the boundary is removed. This approach is motivated by the observation that standard space-time discretization schemes applied to dynamic contact problems yield spurious oscillations. A widely used approach for the numerical simulation of these problems is based on Lagrange multipliers which represent the contact stresses. But the algebraic contact conditions in combination with the inertia volume terms often yield nonphysical results for the contact stresses, and the stability of the algorithm can be lost. Our modified matrix is calculated via nonstandard quadrature formulas that require no extra computational effort. In addition, the conservation properties of the underlying algorithm are carried over to the modified method, and the standard optimal a priori estimates are still satisfied. Numerical examples confirm the optimality of the approach and its stabilization effect applied to contact problems. [ABSTRACT FROM AUTHOR]

In [Carlini, Falcone, Forcadel, and Monneau, SIAM J. Numer. Anal., 46 (2008), pp. 2920-2952], the authors have proposed a generalization of the classical fast marching method of Sethian for the eikonal equation in the case where the normal velocity depends on space and time and can change sign. The goal of this paper is to propose a modified version of the generalized fast marching method proposed in [Carlini, Falcone, Forcadel, and Monneau, SIAM J. Numer. Anal., 46 (2008), pp. 2920-2952] for which we state a general comparison principle. We also prove the convergence of the new algorithm. [ABSTRACT FROM AUTHOR]

The problem of exact controllability of elastic strings has been extensively studied during the last years. We consider the problem of computing numerically the boundary control for a finite-dimensional system obtained by discretizing in space the 1 - d wave equation. More precisely, we analyze whether the controls of numerical approximation schemes converge to the control of the continuous wave equation as the mesh size tends to zero. It is by now well known that, due to high-frequency spurious oscillations, numerical instabilities occur and may lead to the failure of convergence of some apparently natural numerical algorithms. In other words, the classical convergence property of numerical schemes does not guarantee a stable and convergent approximation of controls. Several remedies have been proposed in the literature to compensate for this fact: Tychonoff regularization, Fourier filtering, and mixed finite elements. In this paper we prove that the two-grid method proposed by Glowinski in [J. Comput. Phys., 103 (1992), pp. 189-221] to numerically approximate the control of the wave equation converges in 1 - d. We prove this result in the context of the finite-element space semidiscretization. Our method of proof relies essentially on the particular properties of the Fourier representation of the initial data of the coarse mesh when projected into the fine one. The explicit representation formula of the solutions shows that the high-frequency components are modulated by some weights that diminish the effect of these spurious components. This fact, combined with discrete multipliers techniques, allows us to prove uniform observability inequalities. Classical arguments then allow proving the uniform boundedness of the controls and passing to the limit as the mesh size tends to zero. In this way we prove the convergence of the controls of the finite-element semidiscrete approximation of the 1 - d wave equation with a boundary control on one extreme. It is important to underline that the controls obtained by this two-grid algorithm are not exact in the sense that they only guarantee the controllability of the projection of the solutions into the coarse mesh. [ABSTRACT FROM AUTHOR]

We consider the incompressible Navier-Stokes equations where on a part of the boundary flow rate and mean pressure boundary conditions are prescribed. There are basically two strategies for solving these defective boundary problems: the variational approach (see J. Heywood, R. Rannacher, and S. Turek, Internat. J. Numer. Methods Fluids, 22 (1996), pp. 325-352) and the augmented formulation (see L. Formaggia, J. F. Gerbeau, F. Nobile, and A. Quarteroni, SIAM J. Numer. Anal., 40 (2002), pp. 376-401, and A. Veneziani and C. Vergara, Internat. J. Numer. Methods Fluids, 47 (2005), pp. 803-816). However, both of these approaches present some drawbacks. For the flow rate problem, the former resorts to nonstandard functional spaces, which are quite difficult to discretize. On the other hand, for the mean pressure problem, it yields exact solutions only in very special cases. The latter is applicable only to the flow rate problem, since for the mean pressure problem it provides unfeasible boundary conditions. In this paper, we propose a new strategy based on a reformulation of the problems at hand in terms of the minimization of an appropriate functional. This approach allows us to treat the two kinds of problems (flow rate and mean pressure) successfully within the same framework, which can be useful in view of a mixed problem where the two conditions are simultaneously prescribed on different artificial boundaries. Moreover, it is more versatile, being prone to be extended to other kinds of defective conditions. We analyze the problems obtained with this approach and propose some algorithms for their numerical solution. Several numerical results are presented supporting the effectiveness of our approach. [ABSTRACT FROM AUTHOR]

This paper addresses the question of how to efficiently adapt the conjugate gradient (CG) method to the computation of several leftmost or rightmost eigenvalues and corresponding eigenvectors of Hermitian problems. A generic block CG algorithm instantiated by some available block CG algorithms is considered whereby the new approximate eigenpairs are computed by applying the Rayleigh-Ritz procedure in the trial subspace spanning current approximate eigenvectors and the search direction vectors, each of the latter being a linear combination of the respective gradient of the Rayleigh quotient and all search directions from the previous iteration. An approach related to the so-called Jacobi orthogonal complement correction equation is exploited in the local convergence analysis of this CG algorithm. Based on theoretical considerations, a new block conjugation scheme (a way to compute search directions) is suggested that enjoys a certain kind of optimality and has proved to be competitive in practical eigenvalue computation. [ABSTRACT FROM AUTHOR]

In this paper, a FETI-DP formulation for three dimensional elasticity on nonmatching grids over geometrically nonconforming subdomain partitions is considered. To resolve the nonconformity of the finite elements, a mortar matching condition is imposed on the subdomain interfaces (faces). A FETI-DP algorithm is then built by enforcing the mortar matching condition in dual and primal ways. In order to make the FETI-DP algorithm scalable, a set of primal constraints, which include average and momentum constraints over interfaces, are selected from the mortar matching condition. A condition number bound, C(1 + log(H/h))², is then proved for the FETI-DP formulation for the elasticity problems with discontinuous material parameters. Only some faces need to be chosen as primal faces on which the average and momentum constraints are imposed. Numerical results are included. [ABSTRACT FROM AUTHOR]

In this paper, we study the Legendre-Galerkin spectral approximation for a constrained optimal control problem. We first derive a priori error estimates for the spectral approximation of optimal control problems. Then a posteriori error estimates are obtained for both the state and the control approximation. A preconditioning projection algorithm is proposed with some numerical tests. [ABSTRACT FROM AUTHOR]

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 give explicit constructions of point sets in the s-dimensional unit cube yielding quasi-Monte Carlo algorithms which achieve the optimal rate of convergence of the worst-case error for numerically integrating high-dimensional periodic functions. In the classical measure Pα of the worst-case error introduced by Korobov, the convergence, for every even integer α ⁥ 1, is of …(N-min(α,d) (log N)sα-2), where d is a parameter of the construction which can be chosen arbitrarily large and N is the number of quadrature points. This convergence rate is known to be the best possible up to some log N factors. We prove the result for the deterministic and also a randomized setting. The construction is based on a suitable extension of digital (t, m, s)-nets over the finite field …b. [ABSTRACT FROM AUTHOR]

This paper is devoted to the incorporation of topological derivativelike expansions into level set methods for perimeter-regularized geometric inverse problems. The expansions are done up to the second order with respect to the Lebesgue measure of the symmetric difference. They provide simpler shape functionals, still including the perimeter, and therefore allow the construction of steepest descent- and Newton-type algorithms to force topology changes during the level set evolution. Numerous numerical examples are provided that show the strong and also the weak points of the newly developed algorithms. [ABSTRACT FROM AUTHOR]

In this paper, the authors present two formulations for the Stokes problem which make use of the existing H(div) elements of the Raviart-Thomas type originally developed for the second-order elliptic problems. In addition, two new H(div) elements are constructed and analyzed particularly for the new formulations. Optimal-order error estimates are established for the corresponding finite element solutions in various Sobolev norms. The finite element solutions feature a full satisfaction of the continuity equation when existing Raviart-Thomas-type elements are employed in the numerical scheme. [ABSTRACT FROM AUTHOR]

We study in this paper a new class of waveform relaxation algorithms for large systems of ordinary differential equations arising from discretizations of partial differential equations of advection reaction diffusion type. We show that the transmission conditions between the subsystems have a tremendous influence on the convergence speed of the waveform relaxation algorithms, and we identify transmission conditions with optimal performance. Since these optimal transmission conditions are expensive to use, we introduce a class of local transmission conditions of Robin type, which approximate the optimal ones and can be used at the same cost as the classical transmission conditions. We determine the transmission conditions in this class with the best performance of the associated waveform relaxation algorithm. We show that the new algorithm is well posed and converges much faster than the classical one. We illustrate our analysis with numerical experiments. [ABSTRACT FROM AUTHOR]

In this paper, some two-scale Boolean Galerkin discretizations are proposed and analyzed for a class of Fredholm integral equations of the second kind in multidimensions. It is shown by both theory and numerics that this type of multiscale discretization algorithm not only significantly reduces the number of degrees of freedom but also produces very accurate approximations. [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]

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]

This paper deals with the problem of testing whether a large matrix X has a prescribed structure by looking at the magnitude of a displacement matrix D(X) associated with the structure. We provide parameters on the basis of which one can judge whether the problem is well-conditioned or ill-conditioned. It turns out that even for very general structures it is the minimal eigenvalues of positive definite and banded Toeplitz matrices that are the most important of these parameters. [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]

We introduce a new construction method for digital nets which yield point sets in the s-dimensional unit cube with low star discrepancy. The digital nets are constructed using polynomials over finite fields. It has long been known that there exist polynomials which yield point sets with low (unweighted) star discrepancy. This result was obtained by Niederreiter by the means of averaging over all polynomials. Hence concrete examples of good polynomials were not known in many cases. Here we show that good polynomials can be found by computer search. The search algorithm introduced in this paper is based on minimizing a quantity closely related to the star discrepancy. It has been pointed out that many integration problems can be modeled by weighted function spaces and it has been shown that in this case point sets with low weighted discrepancy are required. Hence it is particularly useful to be able to adjust a point set to some given weights. We are able to extend our results from the unweighted case to show that this can be done using our construction algorithms. This way we can find point sets with low weighted star discrepancy, making such point sets especially useful for many applications. [ABSTRACT FROM AUTHOR]

Numerical constraint systems are often handled by branch and prune algorithms that combine splitting techniques, local consistencies, and interval methods. This paper first recalls the principles of {\tt Quad}, a global constraint that works on a tight and safe linear relaxation of quadratic subsystems of constraints. Then, it introduces a generalization of {\tt Quad} to polynomial constraint systems. It also introduces a method to get safe linear relaxations and shows how to compute safe bounds of the variables of the linear constraint system. Different linearization techniques are investigated to limit the number of generated constraints. {\tt QuadSolver}, a new branch and prune algorithm that combines {\tt Quad}, local consistencies, and interval methods, is introduced. {\tt QuadSolver} has been evaluated on a variety of benchmarks from kinematics, mechanics, and robotics. On these benchmarks, it outperforms classical interval methods as well as constraint satisfaction problem solvers and it compares well with state-of-the-art optimization solvers. [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 considers a multigrid algorithm suitable for efficient solution of indefinite linear systems arising from finite element discretization of time harmonic Maxwell equations. In particular, a "backslash" multigrid cycle is proven to converge at rates independent of refinement level if certain indefinite block smoothers are used. The method of analysis involves comparing the multigrid error reduction operator with that of a related positive definite multigrid operator. This idea has previously been used in multigrid analysis of indefinite second order elliptic problems. However, the Maxwell application involves a nonelliptic indefinite operator. With the help of a few new estimates, the earlier ideas can still be applied. Some numerical experiments with lowest order Nedelec elements are also reported. [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]

The main purpose of this paper is to give numerical algorithms and the error analysis for delay quadratic problems in the calculus of variations. These methods are new, efficient, and accurate and have a global a priori error of O(h²), where h is the distance between any two successive node points. We also derive the results for the general, numerical, delay problem, but we focus on proving our results in the simpler quadratic case since the extra technical numerical details have been given previously by the second author. In addition, the authors have previously shown how to reformulate general delay constrained problems in optimal control theory/constrained calculus of variations as unconstrained delay problems. Thus our numerical results and methods will hold for these general constrained problems also. Finally, we note that our algorithm, which solves the stationary condition(s) numerically, avoids the more difficult problems of piecing the solution of second order equations together and requires less smoothness in the solution. Thus we replace difficult second order boundary value problems with the easier task of approximating definite integrals involving first order derivatives. [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]

This paper establishes an equivalent relation between the convergence of a cascade algorithm in Sobolev space and the convergence of an associated cascade algorithm in L[SUBp] space. It reduces the convergence in Sobolev space to that in L[SUBp] space. On the other hand, by the equivalence we present an algorithm for construction of refinement masks which generate convergent cascade algorithms in Sobolev space. It is very easy to implement the algorithm. Examples are given to illustrate the theory. [ABSTRACT FROM AUTHOR]

In this paper, we develop two least-squares approaches for the solution of the Stokes equations perturbed by a Laplacian term. (Such perturbed Stokes equations arise from finite element approximations of the Reissner­Mindlin plate.) Both are two-stage algorithms that solve first for the curls of the rotation of the fibers and the solenoidal part of the shear strain, then for the rotation itself (if desired). One approach uses L2 norms and the other approach uses H-1 norms to define the least-squares functionals. It is shown that the H-1 norm approach, under general assumptions, and the L2 norm approach, under certain H2 regularity assumptions, admit optimal performance for standard finite element discretization and either standard multigrid solution methods or pre-conditioners. These methods do not degrade when the perturbed parameter (the plate thickness) approaches zero. We also develop a three-stage least-squares method for the Reissner­Mindlin plate, which first solves for the curls of the rotation and the shear strain, next for the rotation itself, and then for the transverse displacement. [ABSTRACT FROM AUTHOR]

This paper is concerned with the application of the fast multipole method (FMM) to the Maxwell equations. This application differs in many aspects from other applications such as the N-body problem, Laplace equation, and quantum chemistry, etc. The FMM leads to a significant speed-up in CPU time with a major reduction in the amount of computer memory needed when performing matrix-vector products. This leads to faster resolution of scattering of harmonic plane waves from perfectly conducting obstacles. Emphasis here is on a rigorous mathematical approach to the problem. We focus on the estimation of the error introduced by the FMM and a rigorous analysis of the complexity (O(n log n)) of the algorithm. We show that error estimates reported previously are not entirely satisfactory and provide sharper and more precise estimates. [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]

This paper is concerned with numerical algorithms for the bipolar quantum drift- diffusion model. For the thermal equilibrium case, a quasi-gradient method minimizing the energy functional is introduced and strong convergence is proved. The computation of current-voltage characteristics is performed by means of an extended Gummel-iteration. It is shown that the involved fixed point mapping is a contraction for small applied voltages. In this case the model equations are uniquely solvable and convergence of the proposed iteration scheme follows. Numerical simulations of a one-dimensional resonant tunneling diode are presented. The computed current-voltage characteristics are in good qualitative agreement with experimental measurements. The appearance of negative differential resistances is verified for the first time in a quantum drift-diffusion model. [ABSTRACT FROM AUTHOR]

The objective of this paper is to develop and analyze a multigrid algorithm for the system of equations arising from the mortar finite element discretization of second order elliptic boundary value problems. In order to establish the inf-sup condition for the saddle point formulation and to motivate the subsequent treatment of the discretizations, we first revisit briefly the theoretical concept of the mortar finite element method. Employing suitable mesh-dependent norms we verify the validity of the Ladyzhenskaya­Babuska­Brezzi (LBB) condition for the resulting mixed method and prove an L2 error estimate. This is the key for establishing a suitable approximation property for our multigrid convergence proof via a duality argument. In fact, we are able to verify optimal multigrid efficiency based on a smoother which is applied to the whole coupled system of equations. We conclude with several numerical tests of the proposed scheme which confirm the theoretical results and show the efficiency and the robustness of the method even in situations not covered by the theory. [ABSTRACT FROM AUTHOR]

In this paper, we present a Gauss­Newton-based BFGS method for solving symmetric nonlinear equations which contain, as a special case, an unconstrained optimization problem, a saddle point problem, and an equality constrained optimization problem. A suitable line search is proposed with which the presented BFGS method exhibits an approximate norm descent property. Under appropriate conditions, global convergence and superlinear convergence of the method are established. The numerical results show that the proposed method is successful. [ABSTRACT FROM AUTHOR]

In computations of fluid flows by domain decomposition methods, the necessity of conservation at grid interfaces is now widely claimed. In this paper we consider nonconservative algorithms for the interfaces. Our investigation begins with discussions about typical nonconservative interface treatments for one-dimensional calculations. The analysis shows that the conservation error of a numerical solution caused by a nonconservative interface matching has an upper bound when the solution itself is bounded. Furthermore, if the numerical solution converges as the mesh size goes to zero, it converges to a weak solution of the problem under certain conditions that may be detected numerically. Also, we acquire similar results for two-dimensional calculations on grids intersecting with each other in an arbitrary way. In order to illustrate the theoretical results, we present numerical examples and demonstrate that, under those conditions, conservation error reduces and accuracy for jumps as well as locations of discontinuities improves as the mesh size decreases. [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]