Search

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]

In this paper we show that the lagged diffusivity fixed point algorithm introduced by Vogel and Oman in [SIAM J. Sci. Comput., 17 (1996), pp. 227­238] to solve the problem of total variation denoising, proposed by Rudin, Osher, and Fatemi in [Phys. D, 60 (1992), pp. 259­268], is a particular instance of a class of algorithms introduced by Voss and Eckhardt in [Computing, 25 (1980), pp. 243­251], whose origins can be traced back to Weiszfeld's original work for minimizing a sum of Euclidean lengths [Tôhoku Math. J., 43 (1937), pp. 355­386]. There have recently appeared several proofs for the convergence of this algorithm [G. Aubert et al., Technical report 94-01, Informatique, Signaux et Systèmes de Sophia Antipolis, 1994], [A. Chambolle and P.-L. Lions, Technical report 9509, CEREMADE, 1995], and [D. C. Dobson and C. R. Vogel, SIAM J. Numer. Anal., 34 (1997), pp. 1779­1791]. Here we present a proof of the global and linear convergence using the framework introduced in [H. Voss and U. Eckhart, Computing, 25 (1980), pp. 243­251] and give a bound for the convergence rate of the fixed point iteration that agrees with our experimental results. These results are also valid for suitable generalizations of the fixed point algorithm. [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]

This paper develops two first-order system least-squares (FOSLS) approaches for the solution of the pure traction problem in planar linear elasticity. Both are two-stage algorithms that first solve for the gradients of displacement (which immediately yield deformation and stress), then for the displacement itself (if desired). One approach, which uses L² norms to define the FOSLS functional, is shown under certain H² regularity assumptions to admit optimal H¹-like performance for standard finite element discretization and standard multigrid solution methods that is uniform in the Poisson ratio for all variables. The second approach, which is based on H-1 norms, is shown under general assumptions to admit optimal uniform performance for displacement flux in an L² norm and for displacement in an HSup1; norm. These methods do not degrade as other methods generally do when the material properties approach the incompressible limit. [ABSTRACT FROM AUTHOR]

The combination technique is an algorithm for the approximate solution of partial differential equations on sparse grids that has to be combined with a suitable standard discretization. The advantage of the combination technique compared to the standard discretization is that the same accuracy is achieved with many fewer grid points. In this paper, the combination technique is used with a bilinear finite element discretization. Depending on the smoothness of the solution and the coefficients, it is proved for general second- order elliptic differential equations on the unit square that the combined solution converges with order O(h) or O(h log h-1) in the energy norm and with order O(h2 log h-1) or O(h 3⁄2 ) in the L2-norm, respectively. This holds even if the bilinear form corresponding to the elliptic equation is not symmetric positive definite. The proof does not use an asymptotic error expansion, but Sobolev space techniques. [ABSTRACT FROM AUTHOR]

Spline collocation differentiation matrices arising when solving PDEs with periodic boundary conditions have block circulant structure. In this paper, we use this fact to present an eigenvalue analysis for a large class of such spline collocation differentiation matrices. We use this to discuss the stability of collocation algorithms for parabolic and hyperbolic problems and fast collocation algorithms for elliptic PDEs. [ABSTRACT FROM AUTHOR]

In this paper the problem of computing bifurcation diagrams for large-scale nonlinear parameter-dependent steady state systems which arise following the spatial discretization of semilinear PDEs is investigated. A continuation algorithm which employs a preconditioned version of the recursive projection method (RPM) is presented. The RPM is often expensive when it is used in conjunction with the numerical method of lines. Preconditioning the Jacobian of the underlying fixed point operator results in an algorithm (the preconditioned recursive projection method (PRPM)) which is capable of efficiently computing equilibrium solution diagrams of large stiff systems. For many PDE problems the PRPM is a fast and effective means of detecting both steady state and Hopf bifurcation along a branch of solutions. A description of the performance of the PRPM when applied to two numerical examples is given. [ABSTRACT FROM AUTHOR]

This paper is concerned with a classical denoising and deblurring problem in image recovery. Our approach is based on a variational method. By using the Legendre­Fenchel transform, we show how the nonquadratic criterion to be minimized can be split into a sequence of half-quadratic problems easier to solve numerically. First we prove an existence and uniqueness result, and then we describe the algorithm for computing the solution and we give a proof of convergence. Finally, we present some experimental results for synthetic and real images. [ABSTRACT FROM AUTHOR]

We study the uniform (Chebyshev) approximation of continuous and piecewise rsmooth (r ≥ 2) functions f : [0, T] → ℝ with a finite number of singular points. The approximation algorithms use only n function values at adaptively or nonadaptively chosen points. We construct a nonadaptive algorithm Anon r,n that, for the functions with at most one singular point, enjoys the best possible convergence rate n-r. This is in sharp contrast to results concerning discontinuous functions. For r ≥ 3, this optimal rate of convergence holds only in the asymptotic sense, i.e., it occurs only for sufficiently large n that depends on f in a way that is practically impossible to verify. However, it is enough to modify Anon r,n by using (r +1)⌊(r - 1)/2⌋ extra function evaluations to obtain an adaptive algorithm Aada r,n with error satisfying ∥ƒ - Aada r,n ƒ∥C ≤ CrTr∥ƒ(r)∥∞L n-r for all n ≥ n0 and n0 independent of f. This result cannot be achieved for functions with more than just one singular point. However, the convergence rate n-r can be recovered asymptotically by a nonadaptive algorithm A non r,n that is a slightly modified Anon r,n . Specifically, lim supn→∞ ∥ƒ -A non r,n ƒ∥C ∙ nr ≤ CrTr∥ƒ(r)∥∞L for all r-smooth functions f with finitely many singular points. [ABSTRACT FROM AUTHOR]

We propose and analyze a pseudotransient continuation algorithm for dynamics on subsets of RN. Examples include certain flows on manifolds and the dynamic formulation of bound-constrained optimization problems. The method gets its global convergence properties from the dynamics and inherits its local convergence properties from any fast locally convergent iteration. [ABSTRACT FROM AUTHOR]

Cyclic nets are a special case of digital nets and were recently introduced by Niederreiter. Here we present a construction algorithm for such nets, where we use the root mean square worst-case error of a randomly digitally shifted point set in a weighted Sobolev space as a selection criterion. This yields a feasible construction algorithm since for a cyclic net with qm points (with fixed bijections and fixed ground field) there are qm possible choices. Our results here match the convergence rate and strong tractability results for polynomial lattice rules, hence providing us with an alternative construction algorithm. Further, we improve upon previous results by including constructions over arbitrary finite fields and an arbitrary choice of bijections. [ABSTRACT FROM AUTHOR]

A cell-centered finite volume method is proposed to approximate numerically the solution to the steady convection-diffusion equation on unstructured meshes of $d$-simplexes, where $d\geq 2$ is the spatial dimension. The method is formally second-order accurate by means of a piecewise linear reconstruction within each cell and at mesh vertices. An algorithm is provided to calculate nonnegative and bounded weights. Face gradients, required to discretize the diffusive fluxes, are defined by a nonlinear strategy that allows us to demonstrate the existence of a maximum principle. Finally, a set of numerical results documents the performance of the method in treating problems with internal layers and solutions with strong gradients. [ABSTRACT FROM AUTHOR]

Using Smolyak's construction [S. A. Smolyak, Dokl. Akad. Nauk SSSR, 4 (1963), pp. 240--243], we derive a new algorithm for approximating multivariate functions over bounded or unbounded regions in $\R^s$ with the error measured in a weighted L1-norm. We provide upper bounds for the algorithm's cost and error for a class of functions whose mixed first order partial derivatives are bounded in the L1-norm. In particular, we prove that the error and the cost (measured in terms of the number of function evaluations) satisfy the relation $$ error \le \frac{s\,\exp\big(\frac1{12(s-1)}\big)}{(s-1)\pi}\, \left(\frac{e\,\ln(\mbox{cost})}{(s-1)\sqrt{2}\ln(2)}\right)^{2(s-1)}\, \frac1{{cost}} $$ whenever the cost is sufficiently large relative to the number s of variables. More specifically, the inequality holds when $q\ge2(s-1)$, where q is a special parameter defining the refinement level in Smolyak's algorithm, and hence the number of function evaluations used by the algorithm. We also discuss extensions of the results to the spaces with the derivatives bounded in Lp-norms. [ABSTRACT FROM AUTHOR]

We derive a Godunov-type numerical flux for the class of strictly convex, homogeneous Hamiltonians that includes H (p, q) = √ap[sup2] + bq[sup2] - 2cpq, c[sup2] < ab. We combine our Godunov numerical fluxes with simple Gauss-Seidel-type iterations for solving the corresponding Hamilton-Jacobi (HJ) equations. The resulting algorithm is fast since it does not require a sorting strategy as found, example, in the fast marching method. In addition, it provides a way to compute solutions to a class of HJ equations for which the conventional fast marching method is not applicable.

We present a monotone waveform relaxation algorithm which produces very tight upper and lower bounds of the transient response of a class of systems described by nonlinear differential- algebraic equations (DAEs) that satisfy certain Lipschitz conditions. The choice of initial iteration is critical and we give two methods of finding it. We show that the class of systems in which monotone convergence of waveform relaxation is possible is actually larger than previously reported. Numerical experiments are given to confirm the monotonicity of convergence of the algorithm. [ABSTRACT FROM AUTHOR]

We formulate and analyze an adaptive nonconforming finite element method for the solution of convex variational problems. The class of minimization problems we admit includes highly singular problems for which no Euler Lagrange equation (or inequality) is available. As a consequence, our arguments only use the structure of the energy functional. We are nevertheless able to prove converge of an adaptive algorithm, using even refinement indicators that are not reliable error indicators. [ABSTRACT FROM AUTHOR]

The energy of the Francfort-Marigo model of brittle fracture can be approximated, in the sense of G-convergence, by the Ambrosio-Tortorelli functional. In this work, we formulate and analyze two adaptive finite element algorithms for the computation of its (local) minimizers. For each algorithm, we combine a Newton-type method with residual-driven adaptive mesh refinement. We present two theoretical results which demonstrate convergence of our algorithms to local minimizers of the Ambrosio-Tortorelli functional. [ABSTRACT FROM AUTHOR]

We introduce hybridization and postprocessing techniques for the Raviart-Thomas approximation of second-order elliptic eigenvalue problems. Hybridization reduces the Raviart- Thomas approximation to a condensed eigenproblem. The condensed eigenproblem is nonlinear, but smaller than the original mixed approximation. We derive multiple iterative algorithms for solving the condensed eigenproblem and examine their interrelationships and convergence rates. An element-by-element postprocessing technique to improve accuracy of computed eigenfunctions is also presented. We prove that a projection of the error in the eigenspace approximation by the mixed method (of any order) superconverges and that the postprocessed eigenfunction approximations converge faster for smooth eigenfunctions. Numerical experiments using a square and an L-shaped domain illustrate the theoretical results. [ABSTRACT FROM AUTHOR]

We consider the convergence of a volume corrected characteristics-mixed method (VCCMM) for advection-diffusion systems. It is known that, without volume correction, the method is first order convergent, provided there is a nondegenerate diffusion term. We consider the advective part of the system and give some properties of the weak solution. With these properties we prove that the volume corrected method, with no diffusion term, gives a lower order L¹-convergence rate of O(h/√Δt + h + (Δt)r), where r is related to the accuracy of the characteristic tracing. This result compares favorably to Godunov's method, but avoids the CFL constraint, so large time steps can be taken in practice. In fact, Godunov's method converges at O(h½), which is our result for Δt = Ch, where now C is not limited. However, the optimal choice, Δt = Ch2/(2r+1), gives a better rate, O(h2r/(2r+1)), than Godunov's method, e.g., O(h2/3) if r = 1. With a nondegenerate diffusion term, we obtain an L²-error estimate for the problem. We also prove the existence of, and give an error estimate for, a perturbed velocity field for which the volume is locally conserved. Finally, some convergence tests are given to verify the optimal convergence rate for r = 1. [ABSTRACT FROM AUTHOR]

We present and analyze an algorithm to solve numerically BSDEs based on Picard's iterations and on a sequential control variate technique. Its convergence is geometric. Moreover, the solution provided by our algorithm is regular both w.r.t. time and space. [ABSTRACT FROM AUTHOR]

Polynomials with quaternionic coefficients located on only one side of the powers (we call them simple polynomials) may have two different types of zeros: isolated and spherical zeros. We will give a new characterization of the types of the zeros and, based on this characterization, we will present an algorithm for producing all zeros including their types without using an iteration process which requires convergence. The main tool is the representation of the powers of a quaternion as a real, linear combination of the quaternion and the number one (as introduced by Pogorui and Shapiro [Complex Var. and Elliptic Funct., 49 (2004), pp. 379-389]) and the use of a real companion polynomial which already was introduced for the first time by Niven [Amer. Math. Monthly, 48 (1941), pp. 654-661]. There are several examples. [ABSTRACT FROM AUTHOR]

We study numerical methods for a coupled Navier-Stokes/Darcy model which describes a fluid flow filtrating through porous media. A decoupled and linearized two-grid algorithm is proposed. Numerical analysis and experiments are presented to show the efficiency and effectiveness of the decoupled and linearized algorithm. [ABSTRACT FROM AUTHOR]

The solution set V of a polynomial system, i.e., the set of common zeroes of a set of multivariate polynomials with complex coefficients, may contain several components, e.g., points, curves, surfaces, etc. Each component has attached to it a number of quantities, one of which is its dimension. Given a numerical approximation to a point p on the set V, this article presents an efficient algorithm to compute the maximum dimension of the irreducible components of V which pass through p, i.e., a local dimension test. Such a test is a crucial element in the homotopy-based numerical irreducible decomposition algorithms of Sommese, Verschelde, and Wampler. This article presents computational evidence to illustrate that the use of this new algorithm greatly reduces the cost of so-called "junk-point filtering," previously a significant bottleneck in the computation of a numerical irreducible decomposition. For moderate size examples, this results in well over an order of magnitude improvement in the computation of a numerical irreducible decomposition. As the computation of a numerical irreducible decomposition is a fundamental backbone operation, gains in efficiency in the irreducible decomposition algorithm carry over to the many computations which require this decomposition as an initial step. Another feature of a local dimension test is that one can now compute the irreducible components in a prescribed dimension without first computing the numerical irreducible decomposition of all higher dimensions. For example, one may compute the isolated solutions of a polynomial system without having to carry out the full numerical irreducible decomposition. [ABSTRACT FROM AUTHOR]

The initial boundary value problem for a hyperbolic-type quasilinear equation wtt = φ(∫0π wx2dx)wxx is considered. Its solution is derived by means of a numerical algorithm consisting of the projection method and the difference method for approximation with respect to spatial and time variables, while the resulting discrete system is solved by an iteration process. The accuracy of the proposed algorithm is estimated. [ABSTRACT FROM AUTHOR]

We study a superreplication problem of European options with gamma constraints in mathematical finance. The initially unbounded control problem is set back to a problem involving a viscosity PDE solution with a set of bounded controls. Then a numerical approach is introduced, unconditionally stable with respect to the mesh steps. A generalized finite difference scheme is used since basic finite differences cannot work in our case. Numerical tests illustrate the validity of our approach. [ABSTRACT FROM AUTHOR]

The author proposes stochastic approximation methods of finding the optimal measure change by the exponential tilting for Lévy processes in Monte Carlo importance sampling variance reduction. In accordance with the structure of the underlying Lévy measure, either a constrained or unconstrained algorithm of the stochastic approximation is chosen. For both cases, the almost sure convergence to a unique stationary point is proved. Numerical examples are presented to illustrate the effectiveness of our method. [ABSTRACT FROM AUTHOR]

A BDDC (balancing domain decomposition by constraints) method is developed for elliptic equations, with discontinuous coefficients, discretized by mortar finite element methods for geometrically nonconforming partitions in both two and three space dimensions. The coarse component of the preconditioner is defined in terms of one mortar constraint for each edge/face, which is the intersection of the boundaries of a pair of subdomains. A condition number bound of the form C maxi{(1 + log(Hi/hi))2} is established under certain assumptions on the geometrically nonconforming subdomain partition in the three-dimensional case. Here Hi and hi are the subdomain diameters and the mesh sizes, respectively. In the geometrically conforming case and the geometrically nonconforming cases in two dimensions, no assumptions on the subdomain partition are required. This BDDC preconditioner is also shown to be closely related to the Neumann-Dirichlet version of the FETI-DP algorithm. The results are illustrated by numerical experiments which confirm the theoretical results. [ABSTRACT FROM AUTHOR]

It is known that the generalized Laguerre polynomials can enjoy subexponential growth for large primary index. In particular, for certain fixed parameter pairs (a, z) one has the large-n asymptotic behavior Ln(-a) (-z) ∼ C(a, z)n-a/2-1/4e∞nz We introduce a computationally motivated contour integral that allows efficient numerical Laguerre evaluations yet also leads to the complete asymptotic series over the full parameter domain of subexponential behavior. We present a fast algorithm for symbolic generation of the rather formidable expansion coefficients. Along the way we address the difficult problem of establishing effective (i.e., rigorous and explicit) error bounds on the general expansion. A primary tool for these developments is an "exp-arc" method giving a natural bridge between converging series and effective asymptotics. [ABSTRACT FROM AUTHOR]

We present a new fast-marching algorithm for an eikonal equation with a velocitychanging sign. This first order equation models a front propagation in the normal direction. The algorithm is an extension of the fast-marching method in two respects. The first is that the new scheme can deal with a time-dependent velocity, and the second is that there is no restriction on its change in sign. We analyze the properties of the algorithm, and we prove its convergence in the class of discontinuous viscosity solutions. Finally, we present some numerical simulations of fronts propagating in ℝ². [ABSTRACT FROM AUTHOR]

The leapfrog algorithm, so called because of its geometric nature, for solving a class of optimal control problems is proposed. Initially a feasible trajectory is given and subdivided into smaller pieces. In each subdivision, with the assumption that local optimal controls can easily be calculated, a piecewise-optimal trajectory is obtained. Then the junctions of these smaller pieces of optimal control trajectories are updated through a scheme of midpoint maps. Under some broad assumptions the sequence of trajectories is shown to converge to a trajectory that satisfies the maximum principle. The main advantages of the leapfrog algorithm are that (i) it does not need an initial guess for the costates and (ii) the piecewise-optimal trajectory generated in each iteration is feasible. These are illustrated through a numerical implementation of leapfrog on a problem involving the van der Pol system. [ABSTRACT FROM AUTHOR]

Phase-based upstreaming, which is a commonly used spatial discretization for multiphase flow in reservoir simulation, naturally gives rise to implicit monotone schemes when implicit time-stepping is used. The nonlinear Gauss-Seidel and Jacobi algorithms are shown to converge to a unique bounded solution when applied to the resulting system of equations. Thus, for one dimensional problems, we obtain an alternate, constructive proof that such schemes are well-defined and converge to the entropy solution of the conservation law for arbitrary CFL numbers. The accuracy of phase-based upstream solutions is studied for various spatial and temporal grids, revealing the importance of unconditional stability when nonuniform grids and/or variable porosity is involved. [ABSTRACT FROM AUTHOR]

In the theory for domain decomposition algorithms of the iterative substructuring family, each subdomain is typically assumed to be the union of a few coarse triangles or tetrahedra. This is an unrealistic assumption, in particular if the subdomains result from the use of a mesh partitioner, in which case they might not even have uniformly Lipschitz continuous boundaries. The purpose of this study is to derive bounds for the condition number of these preconditioned conjugate gradient methods which depend only on a parameter in an isoperimetric inequality, two geometric parameters characterizing John and uniform domains, and the maximum number of edges of any subdomain. A related purpose is to explore to what extent well-known technical tools previously developed for quite regular subdomains can be extended to much more irregular subdomains. Some of these results are valid for any John domain, while an extension theorem, which is needed in this study, requires that the subdomains have complements which are uniform. The results, so far, are complete only for problems in two dimensions. Details are worked out for a FETI-DP algorithm and numerical results support the findings. Some of the numerical experiments illustrate that care must be taken when selecting the scaling of the preconditioners in the case of irregular subdomains. [ABSTRACT FROM AUTHOR]

A balancing domain decomposition by constraints (BDDC) algorithm is developed for compressible elasticity problems in three dimensions with mortar discretization on geometrically nonconforming subdomain partitions. Material parameters of the elasticity problems may have jump across the subdomain interface. Coarse basis functions in the BDDC algorithm are constructed from primal constraints on faces, which are similar to the average matching condition and the moment matching condition considered in [A. Klawonn and O. B. Widlund, Comm. Pure Appl. Math., 59 (2006), pp. 1523-1572] and [H. H. Kim, A FETI-DP Formulation of Three Dimensional Elasticity Problems with Mortar Discretization, Technical report, New York University, 2005]. A condition number bound is proved to be C(1+log(H/h))3 for geometrically nonconforming partitions and to be C(1+log(H/h))2 for geometrically conforming partitions. The bound is not affected by the jump of the material parameters across the subdomain interface. Numerical results are included. [ABSTRACT FROM AUTHOR]

This work develops adaptive time stepping algorithms for the approximation of a functional of a diffusion with jumps based on a jump augmented Monte Carlo Euler-Maruyama method, which achieve a prescribed precision. The main result is the derivation of new expansions for the time discretization error, with computable leading order term in a posteriori form, which are based on stochastic flows and discrete dual backward functions. Combined with proper estimation of the statistical error, they lead to efficient and accurate computation of global error estimates, extending the results by A. Szepessy, R. Tempone, and G. E. Zouraris [Comm. Pure Appl. Math., 54 (2001), pp. 1169-1214]. Adaptive algorithms for either deterministic or trajectory-dependent time stepping are proposed. Numerical examples show the performance of the proposed error approximations and the adaptive schemes. [ABSTRACT FROM AUTHOR]

Standard nonlinear schemes for the the simulation of elastodynamic problems have several shortcomings when considering high-speed rotations. To tackle these problems, we use a corotational framework and a corresponding specific linearization to design new energy-conserving numerical schemes. In the two-dimensional case, an algorithm preserving also angular momentum is presented. The existence of a solution for the fully discrete setting of this algorithm is established. Numerical results illustrate the flexibility and efficiency of the proposed algorithms. [ABSTRACT FROM AUTHOR]

A new approximate mortar condition is proposed for the lowest order Crouzeix-Raviart finite element on nonmatching grids, which uses only the nodal values on the interface for the calculation of the mortar projection. This approach allows for improved and more flexible algorithms compared to those for the standard mortar condition where nodal values in the interior of a subdomain, those closest to a mortar side of the subdomain, are also required in the calculation. [ABSTRACT FROM AUTHOR]

A suitable abstract setting of an initial value problem for the first order operator differential equation is introduced for the case when both the unbounded operator coefficient and its domain can depend on the differentiation variable t. A new exponentially convergent algorithm is proposed. The algorithm is based on a generalization of the Duhamel integral for vector-valued functions. The Duhamel-like technique makes it possible to translate the initial problem to an integral equation and then approximate it with exponential accuracy. The theoretical results are illustrated by examples associated with the heat transfer boundary value problems. [ABSTRACT FROM AUTHOR]

In the early 1980s an elementary algorithm for computing conformal maps was discovered by R. Kühnau and the first author. The algorithm is fast and accurate, but convergence was not known. Given points z0, … , z2 in the plane, the algorithm computes an explicit conformal map of the unit disk onto a region bounded by a Jordan curve γ with z0, … , zn ε γ. We prove convergence for Jordan regions in the sense of uniformly close boundaries and give corresponding uniform estimates on the closed region and the closed disc for the mapping functions and their inverses. Improved estimates are obtained if the data points lie on a C¹ curve or a K-quasicircle. The algorithm was discovered as an approximate method for conformal welding; however, it can also be viewed as a discretization of the Loewner differential equation. [ABSTRACT FROM AUTHOR]

The front-tracking method of Glimm et al. is designed for physical applications which are governed by a hyperbolic system of equations in which codimension one (cd-1) jump discontinuities in the solution are important. The core of this method is the curve propagation algorithm. A theoretical analysis is presented here to show that this curve propagation algorithm is stable. Chang and Lindquist developed a new curve propagation algorithm which conserves mass for any grid of finite spacing. We also present a proof to show the new curve propagation algorithm is stable under some conditions. [ABSTRACT FROM AUTHOR]

A residual-type a posteriori error estimator is introduced and analyzed for a discontinuous Galerkin formulation of a model second-order elliptic problem with Dirichlet-Neumann-type boundary conditions. An adaptive algorithm using this estimator together with specific marking and refinement strategies is constructed and shown to achieve any specified error level in the energy norm in a finite number of cycles. The convergence rate is in effect linear with a guaranteed error reduction at every cycle. Results of numerical experiments are presented. [ABSTRACT FROM AUTHOR]

The FETI method with a natural coarse grid is combined with recently proposed optimal algorithms for the solution of bound and/or equality constrained quadratic programming problems in order to develop a scalable solver for elliptic boundary variational inequalities such as those describing equilibrium of a system of bodies in mutual contact. A discretized model problem is first reduced by the duality theory of convex optimization to the quadratic programming problem with bound and equality constraints. The latter is then modified by means of orthogonal projectors to the natural coarse grid introduced by Farhat, Mandel, and Roux [Comput. Methods Appl. Mech. Engrg., 115 (1994), pp. 365-385]. Finally, the classical results on linear scalability for linear problems are extended to boundary variational inequalities. The results are validated by numerical experiments. The experiments also confirm that the algorithm enjoys the same parallel scalability as its linear counterpart. [ABSTRACT FROM AUTHOR]

The original fast sweeping method, which is an efficient iterative method for stationary Hamilton--Jacobi equations, relies on natural ordering provided by a rectangular mesh. We propose novel ordering strategies so that the fast sweeping method can be extended efficiently and easily to any unstructured mesh. To that end we introduce multiple reference points and order all the nodes according to their lp-metrics to those reference points. We show that these orderings satisfy the two most important properties underlying the fast sweeping method: (1) these orderings can cover all directions of information propagating efficiently; (2) any characteristic can be decomposed into a finite number of pieces and each piece can be covered by one of the orderings. We prove the convergence of the new algorithm. The computational complexity of the algorithm is nearly optimal in the sense that the total computational cost consists of O(M) flops for iteration steps and O(MlogM) flops for sorting at the predetermined initialization step which can be efficiently optimized by adopting a linear time sorting method, where M is the total number of mesh points. Extensive numerical examples demonstrate that the new algorithm converges in a finite number of iterations independent of mesh size. [ABSTRACT FROM AUTHOR]