Search

In a recent paper, the authors introduced the recovery method (local energy matching principle) for solving large systems of lattice equations. The idea is to construct a partial differential equation along with a finite element discretization such that the arising system of linear equations has equivalent energy as the original system of lattice equations. Since a vast variety of efficient solvers is available for solving large systems of finite element discretizations of elliptic PDEs, these solvers may serve as preconditioners for the system of lattice equations. In this paper, we will focus on both the theoretical and the numerical dependence of the method on various mesh-dependent parameters, which can be easily computed and monitored during the solution process. Systematic parameter tests have been performed which underline (a) the robustness and the efficiency of the recovery method and (b) the reliability of the control parameters, which are computed in a preprocessing step to predict the performance of the preconditioner based on the recovery method. [ABSTRACT FROM AUTHOR]

In their 2006 paper, Chernyshenko et al. [J. Math. Phys., 48 (2007), 065204, 15 pp]. prove that a sufficiently smooth strong solution of the 3D Navier-Stokes equations is robust with respect to small enough changes in initial conditions and forcing function. They also show that if a regular enough strong solution exists, then Galerkin approximations converge to it. They then use these results to conclude that the existence of a sufficiently regular strong solution can be verified using sufficiently refined numerical computations. In this paper we study the strong solutions with less regularity than those considered in Chernyshenko et al. [J. Math. Phys., 48 (2007), 065204, 15 pp]. We prove a similar robustness result and show the validity of the results relating convergent numerical computations and the existence of the strong solutions. [ABSTRACT FROM AUTHOR]

In this paper we introduce a new class of tensor decompositions. Intuitively, we decompose a given tensor block into blocks of smaller size, where the size is characterized by a set of mode-n ranks. We study different types of such decompositions. For each type we derive conditions under which essential uniqueness is guaranteed. The parallel factor decomposition and Tucker's decomposition can be considered as special cases in the new framework. The paper sheds new light on fundamental aspects of tensor algebra. [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]

For the first time, we present for the general case of fully nonlinear elliptic differential equations of second order a nonstandard C¹ finite element method (FEM). We consider, throughout the paper, two cases in parallel: For convex, bounded, polyhedral domains in Rn, or for C² bounded domains in R², we prove stability and convergence for the corresponding conforming or nonconforming C¹ FEM, respectively. The results for equations and systems of orders 2 and 2m and quadrature approximations appear elsewhere. The classical theory of discretization methods is applied to the differential operator or the combined differential and the boundary operator. The consistency error for satisfied or violated boundary conditions on polyhedral or curved domains has to be estimated. The stability has to be proved in an unusual way. This is the hard core of the paper. Essential tools are linearization, a compactness argument, the interplay between the weak and strong form of the linearized operator, and a new regularity result for solutions of finite element equations. An essential basis for our proofs are Davydov's results for C¹ FEs on polyhedral domains in Rn or of local degree 5 for C² domains in R². Better convergence and extensions to Rn for C² domains are to be expected from his forthcoming results on curved domains. Our proof for the second case in Rn, includes the first essentially as a special case. The method applies to quasi-linear elliptic problems not in divergence form as well. A discrete Newton method is shown to converge locally quadratically, essentially independently of the actual grid size by the mesh independence principle. [ABSTRACT FROM AUTHOR]

In this paper several Nyström methods for the van der Pol equation are considered. In an earlier study by Cai, Aoyagi, and Abe it was shown that the second order Nyström, or leapfrog, method fails to approximate the limit cycle of the van der Pol equation, exhibiting a periodic modulation of the amplitude and sporadic high frequency noise instead. Cai et al. did a linear analysis and concluded that the spurious behavior was due to the interaction of the main part of the solution with a high frequency computational mode. In this paper we also apply a third and fourth order Nyström method to the van der Pol equation. Numerical experiments show that in these cases the high frequency mode causes blowup after some time. The onset of the instability can be delayed by decreasing the time step. We also improve on their analysis of the second order scheme by doing a nonlinear analysis, to wit a discrete multiple scales analysis. By this means we are able to explain the spurious behavior of this system completely. [ABSTRACT FROM AUTHOR]

Relaxed controls have proved to be very useful in studying the existence of optimal controls in optimal control theory. Many positive results have been obtained in the literature. However, negative results have also made their rare appearances. The optimal control problem considered in this paper looks quite simple. Yet, by treating such a problem, we can get interesting results, substantiating our idea as to whether an optimal control exists or not. In our opinion, the method used in the paper can be applied to more generalized cases. [ABSTRACT FROM AUTHOR]

The paper is devoted to optimization problems of the Bolza and Mayer types for evolution systems governed by nonconvex Lipschitzian differential inclusions in Banach spaces under endpoint constraints described by finitely many equalities and inequalities with generally nonsmooth functions. We develop a variational analysis of such problems mainly based on their discrete approximations and the usage of advanced tools of generalized differentiation satisfying comprehensive calculus rules in the framework of Asplund (and hence any reflexive Banach) spaces. In this way we establish extended results on stability of discrete approximations (with the strong W1,2-convergence of optimal solutions under consistent perturbations of endpoint constraints) and derive necessary optimality conditions for nonconvex discrete-time and continuous-time systems in the refined Euler--Lagrange and Weierstrass--Pontryagin forms accompanied by the appropriate transversality inclusions. In contrast to the case of geometric endpoint constraints in infinite dimensions, the necessary optimality conditions obtained in this paper do not impose any nonempty interiority/finite-codimension/ normal compactness assumptions. The approach and results developed in the paper make a bridge between optimal control/dynamic optimization and constrained mathematical programming problems in infinite-dimensional spaces. [ABSTRACT FROM AUTHOR]

We study the asymptotics of the probability that the sum of independent identically distributed random vectors is in a small cube with a vertex at point x in the following two problems. (A) When the relative (normalized) deviations x/n (n is the number of terms in the sum) are in the analyticity domain of the large deviation rate function Λ(α) for the summands (if, in addition, ∣x∣/n → ∞, then one speaks of superlarge deviations). (B) When the alternative possibility takes place, i.e., when x/n is outside the analyticity domain of the function Λ(α). In problems (A) and (B) the asymptotics of the superlarge deviation probabilities (when ∣x/n∣ → ∞), just as the asymptotics of the probabilities of the ‘usual’ large deviation in problem (B) (when x/n is bounded away from the expectation of the summands and remains bounded), in many aspects remained unknown. The present paper, consisting of two parts, is mostly devoted to solving problem (A) for superlarge deviations. In part I we present a solution to problem (A) in the general multivariate case. As the first step, we use the Cramér transform, which enables one to reduce the problem on superlarge deviations of the original sum to that on normal deviations of the sum of the transformed random vectors. Then we use integrolocal or local theorems for sums of random vectors in the triangular array scheme in the normal deviations zone. The required versions of such theorems are contained in [A. A. Borovkov and A. A. Mogulskii, Math. Notes, 79 (2006), pp. 468-482] and in section 5. We also present in part I a scheme for solving problem (B), to which a separate paper will be devoted. In the case when the distribution of the sum is absolutely continuous in a neighborhood of the point x, we study the asymptotics of the respective density at that point. [ABSTRACT FROM AUTHOR]

In this paper we analyze iterative regularization with the Bregman distance of the total variation seminorm. Moreover, we prove existence of a solution of the corresponding flow equation as introduced in [M. Burger, G. Gilboa, S. Osher, and J. Xu, Commun. Math. Sci., 4 (2006), pp. 179-212] in a functional analytical setting using methods from convex analysis. The results are generalized to variational denoising methods with Lp-norm fit-to-data terms and Bregman distance regularization terms. For the associated flow equations well-posedness is derived using recent results on metric gradient flows from [L. Ambrosio, N. Gigli, and G. Savaré, Gradient Flows in Metric Spaces and in the Space of Probability Measures, Lectures in Mathematics ETH Zürich, Birkhäuser Verlag, Basel, 2005]. In contrast to previous work the results of this paper apply for the analysis of variational denoising methods with the Bregman distance under adequate noise assumptions. Aside from the theoretical results we introduce a level set technique based on Bregman distance regularization for denoising of surfaces and demonstrate the efficiency of this method. [ABSTRACT FROM AUTHOR]

This paper gives a new way of showing that certain constant degree graphs are graph expanders. This is done by giving new proofs of expansion for three permutations of the Gabber-Galil expander. Our results give an expansion factor of (Multiple line equation(s) cannot be represented in ASCII text) for subgraphs of these three-regular graphs with (p - 1)² inputs for p prime. The proofs are not based on eigenvalue methods or higher algebra. The same methods show the expected number of probes for unsuccessful search in double hashing is bounded by (Multiple line equation(s) cannot be represented in ASCII text), where a is the load factor. This assumes a double hashing scheme in which two hash functions are randomly and independently chosen from a specified uniform distribution. The result is valid regardless of the distribution of the inputs. This is analogous to Carter and Wegman's result for hashing with chaining. This paper concludes by elaborating on how any sufficiently sized subset of inputs in any distribution expands in the subgraph of the Gabber-Galil graph expander of focus. This is related to any key distribution having expected (Multiple line equation(s) cannot be represented in ASCII text) probes for unsuccessful search for double hashing given the initial random, independent, and uniform choice of two universal hash functions. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of minimization of a nonsmooth function under general nonsmooth constraints when no derivatives of the objective or constraint functions are available. We introduce the mesh adaptive direct search (MADS) class of algorithms which extends the generalized pattern search (GPS) class by allowing local exploration, called polling, in an asymptotically dense set of directions in the space of optimization variables. This means that under certain hypotheses, including a weak constraint qualification due to Rockafellar, MADS can treat constraints by the extreme barrier approach of setting the objective to infinity for infeasible points and treating the problem as unconstrained. The main GPS convergence result is to identify limit points x0302;, where the Clarke generalized derivatives are nonnegative in a finite set of directions, called refining directions. Although in the unconstrained case, nonnegative combinations of these directions span the whole space, the fact that there can only be finitely many GPS refining directions limits rigorous justification of the barrier approach to finitely many linear constraints for GPS. The main result of this paper is that the general MADS framework is flexible enough to allow the generation of an asymptotically dense set of refining directions along which the Clarke derivatives are nonnegative. We propose an instance of MADS for which the refining directions are dense in the hypertangent cone at x0302; with probability 1 whenever the iterates associated with the refining directions converge to a single x0302;. The instance of MADS is compared to versions of GPS on some test problems. We also illustrate the limitation of our results with examples. [ABSTRACT FROM AUTHOR]

SQP methods for the optimal control of the instationary Navier-Stokes equations with pointwise constraints on the control are considered. Due to the presence of the constraints, the quadratic subproblems (QPs) of SQP require a more sophisticated solver when compared to the unconstrained case. In this paper, a semismooth Newton method is proposed for efficiently solving the QPs. The convergence analysis, which is performed in an appropriate function space setting, relies on the concept of slant differentiability for proving locally superlinear convergence of the QP-solver. For the analysis of the outer SQP-iteration a generalized equations approach is utilized. Sufficient conditions for guaranteeing strong regularity of the generalized equation are established which, in turn, allows one to argue a quadratic rate of convergence of the SQP-method. The paper ends with a report on numerical results supporting the theoretical findings. [ABSTRACT FROM AUTHOR]

In the first part of this paper we study the regularity properties of solutions of initial- or boundary-value problems of linear Fredholm integro-differential equations with weakly singular or other nonsmooth kernels. We then use these results in the analysis of a piecewise polynomial collocation method for solving such problems numerically. The main purpose of the paper is the derivation of optimal global convergence estimates and the analysis of the attainable order of convergence of numerical solutions for all values of the nonuniformity parameter of the underlying grid. [ABSTRACT FROM AUTHOR]

Let $\kappa$ be the condition number of an $m$-by-$n$ matrix with independent standard Gaussian entries, either real ($\beta = 1$) or complex ($\beta = 2$). The major result is the existence of a constant $C$ (depending on $m$, $n$, and $\beta$) such that $P[\kappa > x] n$. Traditional methods for solving such nonsquare generalized eigenvalue problems $(A - \lambda B)\underline{v} = \underline{0}$ are expected to lead to no solutions in most cases. In this paper we propose a different treatment: We search for the minimal perturbation to the pair $(A,B)$ such that these solutions are indeed possible. Two cases are considered and analyzed: (i) the case when $n=1$ (vector pencils); and (ii) more generally, the $n>1$ case with the existence of one eigenpair. For both, this paper proposes insight into the characteristics of the described problems along with practical numerical algorithms toward their solution. We also present a simplifying factorization for such nonsquare pencils, and some relations to the notion of pseudospectra. [ABSTRACT FROM AUTHOR]

Over the last few years a great effort has been made to develop monotone high order explicit Runge--Kutta methods by means of their Shu--Osher representations. In this context, the stepsize restriction to obtain numerical monotonicity is normally computed using the optimal representation. In this paper we extend the Shu--Osher representations for any Runge--Kutta method giving sufficient conditions for monotonicity. We show how optimal Shu--Osher representations can be constructed from the Butcher tableau of a Runge--Kutta method. The optimum stepsize restriction for monotonicity is given by the radius of absolute monotonicity of the Runge--Kutta method [L. Ferracina and M. N. Spijker, SIAM J. Numer. Anal., 42 (2004), pp. 1073--1093], and hence if this radius is zero, the method is not monotone. In the Shu--Osher representation, methods with zero radius require negative coefficients, and to deal with them, an extra associate problem is considered. In this paper we interpret these schemes as representations of perturbed Runge--Kutta methods. We extend the concept of radius of absolute monotonicity and give sufficient conditions for monotonicity. Optimal representations can be constructed from the Butcher tableau of a perturbed Runge--Kutta method. [ABSTRACT FROM AUTHOR]

In this paper we investigate numerical methods for solving hyperbolic conservation laws based on finite volumes and optimal recovery. These methods can, for example, be applied in certain ENO schemes. Their approximation properties depend in particular on the reconstruction from cell averages. Hence, this paper is devoted to prove convergence results for such reconstruction processes from cell averages. [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]

In our papers [Inverse Problems, 15 (1999), pp. 309--327] and [Numer. Math., 88 (2001), pp. 347--365] we proposed algorithm {\tt REGINN}, an inexact Newton iteration for the stable solution of nonlinear ill-posed problems. {\tt REGINN} consists of two components: the outer iteration, which is a Newton iteration stopped by the discrepancy principle, and an inner iteration, which computes the Newton correction by solving the linearized system. The convergence analysis presented in both papers covers virtually any linear regularization method as inner iteration, especially Landweber iteration, $\nu$-methods, and Tikhonov--Phillips regularization. In the present paper we prove convergence rates for {\tt REGINN} when the conjugate gradient method, which is nonlinear, serves as inner iteration. Thereby we add to a convergence analysis of {Hanke}, who had previously investigated {\tt REGINN} furnished with the conjugate gradient method [Numer. Funct. Anal. Optim., 18 (1997), pp. 971--993]. By numerical experiments we illustrate that the conjugate gradient method outperforms the $\nu$-method as inner iteration. [ABSTRACT FROM AUTHOR]

First, by using the 2-regularized determinant technique for Hilbert--Schmidt operators, the computation formula, infinite-product convergence, and analyticity of the 2-regularized determinant of the modified harmonic state operator in finite-dimensional linear continuous-time periodic (FDLCP) systems are derived in this paper. Second, based on these results, a 2-regularized Nyquist criterion is established for asymptotic stability analysis of a class of FDLCP systems for the first time. Third, a numeric implementation algorithm for the 2-regularized Nyquist criterion is also proposed via the staircase truncation on the harmonic transfer operator of the FDLCP system concerned. Finally, to illustrate the results of this paper, asymptotic stability of the lossy Mathieu differential equation is investigated. [ABSTRACT FROM AUTHOR]

This paper extends the derivation of the Lagrangian averaged Euler (LAE-$\alpha$) equations to the case of barotropic compressible flows. The aim of Lagrangian averaging is to regularize the compressible Euler equations by adding dispersion instead of artificial viscosity. Along the way, the derivation of the isotropic and anisotropic LAE-$\alpha$ equations is simplified and clarified. The derivation in this paper involves averaging over a tube of trajectories $\eta^\epsilon$ centered around a given Lagrangian flow $\eta$. With this tube framework, the LAE-$\alpha$ equations are derived by following a simple procedure: start with a given action, Taylor expand in terms of small-scale fluid fluctuations $\xi$, truncate, average, and then model those terms that are nonlinear functions of $\xi$. Closure of the equations is provided through the use of flow rules, which prescribe the evolution of the fluctuations along the mean flow. [ABSTRACT FROM AUTHOR]

In this paper, we continue the development of state feedback boundary control laws based on the backstepping methodology, for the stabilization of unstable, parabolic partial differential equations. We consider the linearized Ginzburg--Landau equation, which models, for instance, vortex shedding in bluff body flows. Asymptotic stabilization is achieved by means of boundary control via state feedback in the form of an integral operator. The kernel of the operator is shown to be twice continuously differentiable, and a series approximation for its solution is given. Under certain conditions on the parameters of the Ginzburg--Landau equation, compatible with vortex shedding modelling on a semi-infinite domain, the kernel is shown to have compact support, resulting in partial state feedback. Simulations are provided in order to demonstrate the performance of the controller. In summary, the paper extends previous work in two ways: (1) it deals with two coupled partial differential equations, and (2) under certain circumstances handles equations defined on a semi-infinite domain. [ABSTRACT FROM AUTHOR]

This paper is motivated by questions about averages of stochastic processes which originate in mathematical finance, originally in connection with valuing the so-called Asian options. Starting with [M. Yor, Adv. Appl. Probab., 24 (1992), pp. 509–531], these questions about exponential functionals of Brownian motion have been studied in terms of Bessel processes using the Hartman­Watson theory of [M. Yor, Z. Wahrsch. Verw. Gebiete, 53 (1980), pp. 71–95]. Consequences of this approach for valuing Asian options proper have been spelled out in [H. Geman and M. Yor, Math. Finance, 3 (1993), pp. 349–375] whose Laplace transform results were in fact regarded as a significant advance. Unfortunately, a number of difficulties with the key results of this last paper have surfaced which are now addressed in this paper. One of them in particular is of a principal nature and originates with the Hartman­Watson approach itself: this approach is in general applicable without modifications only if it does not involve Bessel processes of negative indices. The main mathematical contribution of this paper is the development of three principal ways to overcome these restrictions, in particular by merging stochastics and complex analysis in what seems a novel way, and the discussion of their consequences for the valuation of Asian options proper. [ABSTRACT FROM AUTHOR]

This paper studies the limiting behavior of weighted infeasible central paths for semidefinite programming (SDP) obtained from centrality equations of the form X½ SX½ = vW, where W is a fixed positive definite matrix and v>0 is a parameter, under the assumption that the problem has a strictly complementary primal-dual optimal solution. It is shown that a weighted central path as a function of √v can be extended analytically beyond 0 and hence that the path converges as v↓0. Characterization of the limit points of the path and its normalized first-order derivatives are also provided. As a consequence, it is shown that a weighted central path can have two types of behavior: it converges either as &Tetha;(v) or asT &Tetha;(√v) depending on whether the matrix W on a certain scaled space is block diagonal or not, respectively. We also derive an error bound on the distance between a point lying in a certain neighborhood of the central path and the set of primal-dual optimal solutions. Finally, in light of the results of this paper, we give a characterization of a sufficient condition proposed by Potra and Sheng which guarantees the superlinear convergence of a class of primal-dual interior-point SDP algorithms. [ABSTRACT FROM AUTHOR]

In this paper we present a new iteration-complexity bound for the Mizuno--Todd--Ye predictor-corrector (MTY P-C) primal-dual interior-point algorithm for linear programming. The analysis of the paper is based on the important notion of crossover events introduced by Vavasis and Ye. For a standard form linear program min {cTχ: Aχ = b, &chi ≥ 0 } with decision variable ..., we show that the MTY P-C algorithm, started from a well-centered interior-feasible solution with duality gap nμ0 finds an interior-feasible solution with duality gap less than nn in O (T(μ0/η)+n3.5 log (Χ*A)) iterations, where T(t ) =min {n² log (log t), log t} for all t>0 and Χ*A is a scaling invariant condition number associated with the matrix A. More specifically,Χ*A is the infimum of all the conditions numbers XAD, where D varies over the set of positive diagonal matrices. Under the setting of the Turing machine model, our analysis yields an O (n3.5 LA + min {n² log L, L}) iteration-complexity bound for the MTY P-C algorithm to find a primal-dual optimal solution, where LA and L are the input sizes of the matrix A and the data (A,b,c ), respectively. This contrasts well with the classical iteration-complexity bound for the MTY P-C algorithm, which depends linearly on L instead of log L. [ABSTRACT FROM AUTHOR]

We consider processes in which a focused laser beam is used to induce the melting of silicium. The first goal of this paper is to propose a simple three-dimensional (3D) model of this melting process. Our model is partly based on an energy balance equation. This model leads to a nontrivial ODE describing the evolution in time of the dimension of the melt region. The second goal of this paper is to obtain approximate analytical solutions of this ODE. After using basic solution methods, we propose an original geometrical method to derive asymptotic solutions for time → ∞. These solutions turn out to be the most useful for the description of this process. [ABSTRACT FROM AUTHOR]

Abstract. This paper considers a fractional distribution of an s-dimensional Gaussian random vector. Inequalities for the distribution deviation from the uniform distribution are proved. The proofs use the Poisson summation formula and some facts from the theory of representation of integers by square forms. The main attention of this part of the paper is devoted to the case of small values of s. The case of large values of s will be consider additionally. [ABSTRACT FROM AUTHOR]

This paper continues the analysis started in the first part of this article (cf. [J. J. L. Velázquez, SIAM J. Appl. Math., 64 (2004), pp. 1198-1223]). It was seen there, using the method of matched asymptotics, that a regularized version of the Keller-Segel system admits, for a suitable asymptotic limit, solutions with some regions of high concentrations for the cell density. This paper considers the relation between the phenomenon of blow-up for the limit problem and the dynamics of the concentration regions described in [J. J. L. Velázquez, SIAM J. Appl. Math., 64 (2004), pp. 1198- 1223]. In particular, this paper analyzes the precise way in which the regularization introduced in the Keller-Segel system stops the aggregation process and yields the formation of concentration regions. [ABSTRACT FROM AUTHOR]

Let M be a 2 × 2 matrix of Laurent polynomials with real coefficients and symmetry. In this paper, we obtain a necessary and sufficient condition for the existence of four Laurent polynomials (or finite-impulse-response filters) u1, u2, v1, v2 with real coefficients and symmetry such that [This symbol cannot be presented in ASCII format] and [Su1](z)[Sv2](z) = [Su2](z)[Sv1](z), where [Sp](z) = p(z)/p(1/z) for a nonzero Laurent polynomial p. Our criterion can be easily checked and a step-by-step algorithm will be given to construct the symmetric filters u1, u2, v1, v2. As an application of this result to symmetric framelet filter banks, we present a necessary and sufficient condition for the construction of a symmetric multiresolution analysis tight wavelet frame with two compactly supported generators derived from a given symmetric refinable function. Once such a necessary and sufficient condition is satisfied, an algorithm will be used to construct a symmetric framelet filter bank with two high-pass filters which is of interest in applications such as signal denoising and image processing. As an illustration of our results and algorithms in this paper, we give several examples of symmetric framelet filter banks with two highpass filters which have good vanishing moments and are derived from various symmetric low-pass filters including some B-spline filters. [ABSTRACT FROM AUTHOR]

We study second order sufficient optimality conditions (SSC) for optimal control problems with control appearing linearly. Specifically, time-optimal bang-bang controls will be investigated. In [N. P. Osmolovskii, Sov. Phys. Dokl., 33 (1988), pp. 883-885; Theory of HigherOrder Conditions in Optimal Control, Doctor of Sci. thesis, Moscow, 1988 (in Russian); Russian J. Math. Phys., 2 (1995), pp. 487-516; Russian J. Math. Phys., 5 (1997), pp. 373-388; Proceedings of the Conference "Calculus of Variations and Optimal Control," Chapman & Hall/CRC, Boca Raton, FL, 2000, pp. 198-216; A. A. Milyutin and N. P. Osmolovskii, Calculus of Variations and Optimal Control, Transl. Math. Monogr. 180, AMS, Providence, RI, 1998], SSC have been developed in terms of the positive definiteness of a quadratic form on a critical cone or subspace. No systematical numerical methods for verifying SSC are to be found in these papers. In the present paper, we study explicit representations of the critical subspace. This leads to an easily implementable test for SSC in the case of a bang-bang control with one or two switching points. In general, we show that the quadratic form can be simplified by a transformation that uses a solution to a linear matrix differential equation. Particular conditions even allow us to convert the quadratic form to perfect squares. Three numerical examples demonstrate the numerical viability of the proposed tests for SSC. [ABSTRACT FROM AUTHOR]

The goal of this paper is to develop a theoretical framework in order to analyze cooperative games in which only certain coalitions are allowed to form. We will axiomatize the structure of such allowable coalitions using the theory of antimatroids, a notion developed for combinatorially abstract sets. There have been previous models developed to confront the problem of unallowable coalitions. Games restricted by a communication graph were introduced by Myerson and Owen. We introduce a new combinatorial structure called augmenting system, which is a generalization of the antimatroid structure and the system of connected subgraphs of a graph. The main result of the paper is a direct formula of Shapley and Banzhaf values for games under augmenting systems restrictions. [ABSTRACT FROM AUTHOR]

We present support theory, a set of techniques for bounding extreme eigenvalues and condition numbers for matrix pencils. Our intended application of support theory is to enable proving condition number bounds for preconditioners for symmetric, positive definite systems. One key feature sets our approach apart from most other works: We use support numbers instead of generalized eigenvalues. Although closely related, we believe support numbers are more convenient to work with algebraically. This paper provides the theoretical foundation of support theory and describes a set of analytical tools and techniques. For example, we present a new theorem for bounding support numbers (generalized eigenvalues) where the matrices have a known factorization (not necessarily square or triangular). This result generalizes earlier results based on graph theory. We demonstrate the utility of this approach by a simple example: block Jacobi preconditioning on a model problem. Also, our analysis of a new class of preconditioners, maximum-weight basis preconditioners, in [E. G. Boman, D. Chen, B. Hendrickson, and S. Toledo, Numer. Linear Algebra Appl., to appear] is based on results contained in this paper. [ABSTRACT FROM AUTHOR]

This paper, which can be considered a continual, ion of the papers [C. A. Stuart, J. Math. Pures Appl., 80 (2001), pp. 281-337] and [C. A. Stuart, Proc. Roy. Soc. Edinburgh Sect. A, 132 (2002), pp. 729 7(14], is concerned with the study of the buckling of a tapered rod. This physical phenomenon leads to tile nonlinear eigenvalue problem {A(s)u'(s)}' + μsin u(s) = 0 for all s ∈ (0, 1), u(1) = lim A(s)u'(s) = 0, s → 0 ∫ [sup1 sub0] A(s)'(s)²ds < ∞ where A(s) ∈ C([0, 1]) is such t, hat, A(s) > 0 for all s > 0 and lim[s sub&rarr0] A(s)/s[supp] = L for some constants p ≥ 0 and L ∈ (0, ∞). We study the set of all solutions of tile problem and, in particular, find tile points μ ∈ R[sub+] such that bifurcation occurs at, (μ, 0). As was shown by Stuart in [J. Math. Pures Appl., 80 (2001), pp. 281 387], there is a number A(A) ≥ 0 such that, for μ ≤ A(A), μ ≡ 0 is the only solution of the problem, and it minimizes the energy in the space of all admissible configurations. For μ > A(A), the energy is minimized by a nontrivial solution. For 0 ≤ p < 2, bifurcation occurs at a discrete set of eigenvalues μ[subi], i ∈ N* = {1,2,...}, which satisfy μ1 A(A), μ[subi] < μ[subi]+1 for all i ∈ N* and lim[subi → ∞] μ[subi] = ∞. At p 2, changes occur. For 0 ≤ p le; 2, A(A) > 0, whereas A(A) = 0 for p > 2. For p 2, there is a number A[sube;(A) ∈ [A(A),∞) such that bifurcation occurs at every value μ ∈ [A[sube](A), ∞). In this paper, we show tile following points: • For p = 2, if A(A) < A[sube](A), bifurcation from the solution u ≡ 0 also occurs at a finite or countable set, of eigenvalues μ[subi] I ⊂ N*,... [ABSTRACT FROM AUTHOR]

This paper contains a new convergence analysis for the Lewis and Torczon generalized pattern search (GPS) class of methods for unconstrained and linearly constrained optimization. This analysis is motivated by a desire to understand the successful behavior of the algorithm under hypotheses that are satisfied by many practical problems. Specifically, even if the objective function is discontinuous or extended-valued, the methods find a limit point with some minimizing properties. Simple examples show that the strength of the optimality conditions at a limit point depends not only on the algorithm, but also on the directions it uses and on the smoothness of the objective at the limit point in question. The contribution of this paper is to provide a simple convergence analysis that supplies detail about the relation of optimality conditions to objective smoothness properties and to the defining directions for the algorithm, and it gives previous results as corollaries. [ABSTRACT FROM AUTHOR]

Let gd(n) be the set of d-regular simple graphs with n vertices, and for G = (V, E) in gd(n) let f : → {1, 2, . . . , n} be a objective coloring of the vertices of G. Also let α denote an interference parameter in {0, 1,. . . ,n - 1}, and define the interference number of f with respect to G and α as the number of edges {u, v} in E for which min{/f(u) - f(v)\,n - f(u) - f(v)\} < α. We consider two interference number problems for feasible (n, α, d). The first is to specify a G E and an f for which the interference number is as small as possible. The second is to determine a G &epsiv; gd(n) whose minimum interference number over all f is as large as possible. A previous paper completely solves both problems for d = 2. The present paper solves the first problem for all d ≥ 3 and obtains partial results for the second problem for d ≥ 3 that focus on interference-minimizing f's when G consists of disjoint copies of Kd+1. [ABSTRACT FROM AUTHOR]

It was recently shown that a family of exponentially stable linear systems whose matrices generate a solvable Lie algebra possesses a quadratic common Lyapunov function, which implies that the corresponding switched linear system is exponentially stable for arbitrary switching. In this paper we prove that the same properties hold under the weaker condition that the Lie algebra generated by given matrices can be decomposed into a sum of a solvable ideal and a subalgebra with a compact Lie group. The corresponding local stability result for nonlinear switched systems is also established. Moreover, we demonstrate that if a Lie algebra fails to satisfy the above condition, then it can be generated by a family of stable matrices such that the corresponding switched linear system is not stable. Relevant facts from the theory of Lie algebras are collected at the end of the paper for easy reference. [ABSTRACT FROM AUTHOR]

Given a directed graph G and an arc weight function w : E(G) → R+, the maximum directed cut problem (max dicut) is that of finding a directed cut δ(X) with maximum total weight. In this paper we consider a version of max dicut--max dicut with given sizes of parts or max dicut with gsp--whose instance is that of max dicut plus a positive integer p, and it is required to find a directed cut δ(X) having maximum weight over all cuts δ(X) with |X| = p. Our main result is a 0.5-approximation algorithm for solving the problem. The algorithm is based on a tricky application of the pipage rounding technique developed in some earlier papers by two of the authors and a remarkable structural property of basic solutions to a linear relaxation. The property is that each component of any basic solution is an element of a set {0,δ, 1/2, 1 - δ, 1}, where δ is a constant that satisfies 0 < δ < 1/2 and is the same for all components. [ABSTRACT FROM AUTHOR]

In this paper, we examine different methods using techniques of blocking, buffering, and padding for efficient implementations of bit-reversals. We evaluate the merits and limits of each technique and its application and architecture-dependent conditions for developing cache-optimal methods. Besides testing the methods on different uniprocessors, we conducted both simulation and measurements on two commercial symmetric multiprocessors (SMP) to provide architectural insights into the methods and their implementations. We present two contributions in this paper: (1) Our integrated blocking methods, which match cache associativity and translation-lookaside buffer (TLB) cache size and which fully use the available registers, are cache-optimal and fast. (2) We show that our padding methods outperform other software-oriented methods, and we believe they are the fastest in terms of minimizing both CPU and memory access cycles. Since the padding methods are almost independent of hardware, they could be widely used on many uniprocessor workstations and multiprocessors. [ABSTRACT FROM AUTHOR]

In this paper we apply the generalized Taylor­Galerkin finite element model to simulate bore wave propagation in a domain of two dimensions. For stability and accuracy reasons, we generalize the model through the introduction of four free parameters. One set of parameters is rig- orously determined to obtain the high-order finite element solution. The other set of free parameters is determined from the underlying discrete maximum principle to obtain the monotonic solutions. The resulting two models are used in combination through the flux correct transport technique of Zalesak, thereby constructing a finite element model which has the ability to capture hydraulic dis- continuities. In addition, this paper highlights the implementation of two Krylov subspace iterative solvers, namely, the bi-conjugate gradient stabilized (Bi-CGSTAB) and the generalized minimum residual (GMRES) methods. For the sake of comparison, the multifrontal direct solver is also con- sidered. The performance characteristics of the investigated solvers are assessed using results of a standard test widely used as a benchmark in hydraulic modeling. Based on numerical results, it is shown that the present finite element method can render the technique suitable for solving shallow water equations with sharply varying solution profiles. Also, the GMRES solver is shown to have a much better convergence rate than the Bi-CGSTAB solver, thereby saving much computing time compared to the multifrontal solver. [ABSTRACT FROM AUTHOR]

In this paper we study the inversion of an analytic matrix valued function A(z). This problem can also be viewed as an analytic perturbation of the matrix A0 = A(0). We are mainly interested in the case where A0 is singular but A(z) has an inverse in some punctured disc around z = 0. It is known that A-1 (z) can be expanded as a Laurent series at the origin. The main purpose of this paper is to provide efficient computational procedures for the coefficients of this series. We demonstrate that the proposed algorithms are computationally superior to symbolic algebra when the order of the pole is small. [ABSTRACT FROM AUTHOR]

This paper studies the solution of quadratic eigenvalue problems by the quadratic residual iteration method. The focus is on applications arising from finite-element simulations in acoustics. One approach is the shift-and-invert Arnoldi method applied to the linearized problem. When more than one eigenvalue is wanted, it is advisable to use locking or deflation of converged eigenvectors (or Schur vectors). In order to avoid unlimited growth of the subspace dimension, one can restart the method by purging unwanted eigenvectors (or Schur vectors). Both locking and restarting use the partial Schur form. The disadvantage of this approach is that the dimension of the linearized problem is twice that of the quadratic problem. The quadratic residual iteration and Jacobi­Davidson methods directly solve the quadratic problem. Unfortunately, the Schur form is not defined, nor are locking and restarting. This paper shows a link between methods for solving quadratic eigenvalue problems and the linearized problem. It aims to combine the benefits of the quadratic and the linearized approaches by employing a locking and restarting scheme based on the Schur form of the linearized problem in quadratic residual iteration and Jacobi­Davidson. Numerical experiments illustrate quadratic residual iteration and Jacobi­Davidson for computing the linear Schur form. It also makes a comparison with the shift-and-invert Arnoldi method. [ABSTRACT FROM AUTHOR]

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

The implicitly shifted (bulge-chasing) QZ algorithm is the most popular method for solving the generalized eigenvalue problem Av = λBv. This paper explains why the QZ algorithm functions well even in the presence of infinite eigenvalues. The key to rapid convergence of QZ (and QR) algorithms is the effective transmission of shifts during the bulge chase. In this paper the mechanism of transmission of shifts is identified, and it is shown that this mechanism is not disrupted by the presence of infinite eigenvalues. Both the QZ algorithm and the preliminary reduction to Hessenberg-triangular form tend to push the infinite eigenvalues toward the top of the pencil. Thus they should be deflated at the top. [ABSTRACT FROM AUTHOR]

Two first-order system least squares (FOSLS) methods based on L2 norms are applied to various boundary value problems of planar linear elasticity. Both use finite element discretization and multigrid solution methods. They are two-stage algorithms that solve first for the displacement flux variable (the gradient of displacement, which easily yields the deformation and stress variables), then for the displacement variable itself. As a complement to a companion theoretical paper, this paper focuses on numerical results, including finite element accuracy and multigrid convergence estimates that confirm uniform optimal performance-even as the material tends to the incompressible limit. [ABSTRACT FROM AUTHOR]

The graph of linear extensions G(P) of a poset P has as vertices the linear extensions of P, and two vertices are adjacent if they differ only by an adjacent transposition. This graph has so far been investigated mainly with respect to Hamilton paths and intrinsic geodesic convexity. The work on the latter topic especially shows how the graph-theoretic properties of G(P) reflect the order-theoretic structure of P. The aim of this paper is to study the graph G(P) with respect to topics from classical graph theory, e.g., connectivity, cycle space, isometric embeddings, and to find order-theoretic interpretations of these notions. The main theorems in this paper are the equality of the connectivity of G(P) and the jump number of P, the existence of a certain generating system for the cycle space, and a relationship of P and its subposets obtained via an embedding of the graph of linear extensions. [ABSTRACT FROM AUTHOR]

Dynamical systems can often be decomposed into loosely coupled subsystems. The system of ordinary differential equations (ODEs) modelling such a problem can then be partitioned corresponding to the subsystems, and the loose couplings can be exploited by special integration methods to solve the problem using a parallel computer or just solve the problem more efficiently than by standard methods. This paper presents accuracy analysis of methods for the numerical integration of stiff partitioned systems of ODEs. The discretization formulas are based on the implicit Euler formula and the second order implicit backward differentiation formula (BDF2). Each subsystem of the partitioned problem is discretized independently, and the couplings to the other subsystems are based on solution values from previous time steps. Applied this way, the discretization formulas are called decoupled. The stability properties of the decoupled implicit Euler formula are well understood. This paper presents error bounds and asymptotic error expansions to be used in controlling step size, relaxation between subsystems and the validity of the partitioning. The decoupled BDF2 formula is analyzed within the same framework. Finally, the analysis is used in the design of a decoupled numerical integration algorithm with variable step size to control the local error and adaptive selection of partitionings. Two versions of the algorithm with decoupled implicit Euler and BDF2, respectively, are used in examples where a realistic problem is solved. The examples compare the results from the decoupled implicit Euler and BDF2 formulas, and compare them with results from the corresponding classical formulas. [ABSTRACT FROM AUTHOR]

We consider the shape-topological control of a singularly perturbed variational inequality. The geometry-dependent state problem that we address in this paper concerns a heterogeneous medium with a micro-object (defect) and a macro-object (crack) modeled in two dimensions. The corresponding nonlinear optimization problem subject to inequality constraints at the crack is considered within a general variational framework. For the reason of asymptotic analysis, singular perturbation theory is applied, resulting in the topological sensitivity of an objective function representing the release rate of the strain energy. In the vicinity of the nonlinear crack, the antiplane strain energy release rate is expressed by means of the mode-III stress intensity factor that is examined with respect to small defects such as microcracks, holes, and inclusions of varying stiffness. The result of shape-topological control is useful either for arrests or rise of crack growth. [ABSTRACT FROM AUTHOR]

In this paper, we consider the finite-dimensional approximations of Tikhonov regularization for nonlinear ill-posed problems with approximately given right-hand sides. We propose an a posteriori parameter choice strategy, which is a modified form of Morozov's discrepancy principle, to choose the regularization parameter. Under certain assumptions on the nonlinear operator, we obtain the convergence and rates of convergence for Tikhonov regularized solutions. This paper extends the results, which were developed by Plato and Vainikko in 1990 for solving linear ill-posed equations, to nonlinear problems. [ABSTRACT FROM AUTHOR]

Families of matrices smoothly depending on a vector of parameters are considered. Arnold [Russian Math. Surveys, 26 (1971), pp. 29–43] and Galin [Uspekhi Mat. Nauk, 27 (1972),pp. 241–242] have found and listed normal forms of families of complex and real matrices (miniversal deformations), to which any family of matrices can be transformed in the vicinity of a point in the parameter space by a change of basis, smoothly dependent on a vector of parameters, and by a smooth change of parameters. In this paper a constructive method of determining functions describing a change of basis and a change of parameters, transforming an arbitrary family to the miniversal deformation, is suggested. Derivatives of these functions with respect to parameters are determined from a recurrent procedure using derivatives of the functions of lower orders and derivatives of the family of matrices. Then the functions are found as Taylor series. Examples are given. The suggested method allows using efficiently miniversal deformations for investigation of different properties of matrix families. This is shown in the paper where tangent cones (linear approximations) to the stability domain at the singular boundary points are found. [ABSTRACT FROM AUTHOR]

This paper is concerned with refinement equations of the type [This symbol cannot be presented in ASCII format] where f is the unknown function defined on the s-dimensional Euclidean space Rs, a is a finitely supported sequence on Zs, and M is an s × s dilation matrix with m := | det M|. The solution of a refinement equation can be obtained by using the subdivision scheme associated with the mask. In this paper we give a characterization for the convergence of the subdivision scheme when the mask is nonnegative. Our method is to relate the problem of convergence to m column-stochastic matrices induced by the mask. In this way, the convergence of the subdivision scheme can be determined in a finite number of steps by checking whether each finite product of those column-stochastic matrices has a positive row. As a consequence of our characterization, we show that the convergence of the subdivision scheme with a nonnegative mask depends only on the location of its positive coefficients. Several examples are provided to demonstrate the power and applicability of our approach. [ABSTRACT FROM AUTHOR]