Search

The article highlights two papers published within the issue titled "Divide-and-Conquer: A Proportional, Minimal-Envy Cake-Cutting Algorithm," by Steven Brams, Michael Jones and Christian Klamler, and "Impossibility of Fast Stable Approximation of Analytic Functions from Equispaced Samples," by Rodrigo Platte, Lloyd Trefethen and Arno Kuijlaars. The first paper discussed the mathematical problem of proportional division. The second one talked about potential theory, matrix iterations in the form of Krylov space methods and quadrature formulae.

This paper considers the finite element approximation and algebraic solution of the pure Neumann problem. Our goal is to present a concise variational framework for the finite element solution of the Neumann problem that focuses on the interplay between the algebraic and variational problems. While many of the results that stem from our analysis are known by some experts, they are seldom derived in a rigorous fashion and remain part of numerical folklore. As a result, this knowledge is not accessible (or appreciated) by many practitioners--both novices and experts--in one source. Our paper contributes a simple, yet insightful link between the continuous and algebraic variational forms that will prove useful. [ABSTRACT FROM AUTHOR]

In this paper we show that a generalization of a popular motion planning puzzle called Lunar Lockout is computationally intractable. In particular, we show that the problem is PSPACE-complete. We begin with a review of NP-completeness and polynomial-time reductions, introduce the class PSPACE, and motivate the significance of PSPACE-complete problems. Afterwards, we prove that determining whether a given instance of a generalized Lunar Lockout puzzle is solvable is PSPACE-complete. [ABSTRACT FROM AUTHOR]

The work in this paper concerns the study of conventional and refined heat balance integral methods for a number of phase change problems. These include standard test problems, both with one and two phase changes, which have exact solutions that enable us to test the accuracy of the approximate solutions. We also consider situations where no analytical solution is available and compare these to numerical solutions. It is popular to use a quadratic profile as an approximation of the temperature, but we show that a cubic profile, seldom considered in the literature, is far more accurate in most circumstances. In addition, the refined integral method can give greater improvement still, and we develop a variation on this method which turns out to be optimal in some cases. We assess which integral method is better for various problems, showing that it is largely dependent on the specified boundary conditions. [ABSTRACT FROM AUTHOR]

Hybrid dynamical systems are systems that combine features of continuous-time dynamical systems and discrete-time dynamical systems, and can be modeled by a combination of differential equations or inclusions, difference equations or inclusions, and constraints. Preasymptotic stability is a concept that results from separating the conditions that asymptotic stability places on the behavior of solutions from issues related to existence of solutions. In this paper, techniques for approximating hybrid dynamical systems that generalize classical linearization techniques are proposed. The approximation techniques involve linearization, tangent cones, homogeneous approximations of functions and set-valued mappings, and tangent homogeneous cones, where homogeneity is considered with respect to general dilations. The main results deduce preasymptotic stability of an equilibrium point for a hybrid dynamical system from preasymptotic stability of the equilibrium point for an approximate system. Further results relate the degree of homogeneity of a hybrid system to the Zeno phenomenon that can appear in the solutions of the system. [ABSTRACT FROM AUTHOR]

This paper surveys some results on acute and nonobtuse simplices and associated spatial partitions. These partitions are relevant in numerical mathematics, including piecewise polynomial approximation theory and the finite element method. Special attention is paid to a basic type of nonobtuse simplices called path-simplices, the generalization of right triangles to higher dimensions. In addition to applications in numerical mathematics, we give examples of the appearance of acute sad nonobtuse simplices in other areas of mathematics. [ABSTRACT FROM AUTHOR]

This paper presents some known results on the approximate and null controllability of the Navier­Stokes equations. All of them can be viewed as partial answers to a conjecture of J.-L. Lions. [ABSTRACT FROM AUTHOR]

We present a mathematical and computational framework for learning a dynamical system from noisy observations of a few trajectories and subject to side information. Side information is any knowledge we might have about the dynamical system we would like to learn, besides trajectory data, and is typically inferred from domain-specific knowledge or basic principles of a scientific discipline. We are interested in explicitly integrating side information into the learning process in order to compensate for scarcity of trajectory observations. We identify six types of side information that arise naturally in many applications and lead to convex constraints in the learning problem. First, we show that when our model for the unknown dynamical system is parameterized as a polynomial, we can impose our side information constraints computationally via semidefinite programming. We then demonstrate the added value of side information for learning the dynamics of basic models in physics and cell biology, as well as for learning and controlling the dynamics of a model in epidemiology. Finally, we study how well polynomial dynamical systems can approximate continuously differentiable ones while satisfying side information (either exactly or approximately). Our overall learning methodology combines ideas from convex optimization, real algebra, dynamical systems, and functional approximation theory, and can potentially lead to new synergies among these areas. [ABSTRACT FROM AUTHOR]

Motivated by applications in quantum chemistry and solid state physics, we apply general results from approximation theory and matrix analysis to the study of the decay properties of spectral projectors associated with large and sparse Hermitian matrices. Our theory leads to a rigorous proof of the exponential off-diagonal decay ("nearsightedness") for the density matrix of gapped systems at zero electronic temperature in both orthogonal and nonorthogonal representations, thus providing a firm theoretical basis for the possibility of linear scaling methods in electronic structure calculations for nonmetallic systems. We further discuss the case of density matrices for metallic systems at positive electronic temperature. A few other possible applications are also discussed. [ABSTRACT FROM AUTHOR]

A collection of typical examples shows the exotic behavior of numerical methods when applied to singular perturbation problems. While standard meshes are used in the first six examples, even on layer-adapted meshes several surprising phenomena are shown to occur. [ABSTRACT FROM AUTHOR]

The article presents an abstract on the notions of P and NP, one of the most famous concepts in theoretical computer science. If a problem is in P, it means that there is an efficient algorithm to solve the problem, while if it is NP, there is an efficient algorithm to check whether a potential solution is a solution.

The scaling and squaring method is the most widely used method for computing the matrix exponential, not least because it is the method implemented in the MATLAB function expm. The method scales the matrix by a power of 2 to reduce the norm to order 1, computes a Padé approximant to the matrix exponential, and then repeatedly squares to undo the effect of the scaling. We give a new backward error analysis of the method (in exact arithmetic) that employs sharp bounds for the truncation errors and leads to an implementation of essentially optimal efficiency. We also give a new rounding error analysis that shows the computed Padé approximant of the scaled matrix to be highly accurate. For IEEE double precision arithmetic the best choice of degree of Padé approximant turns out to be 13, rather than the 6 or 8 used by previous authors. Our implementation of the scaling and squaring method always requires at least two fewer matrix multiplications than the expm function in MATLAB 7.0 when the matrix norm exceeds 1, which can amount to a 37% saving in the number of multiplications, and it is typically more accurate, owing to the fewer required squarings. We also investigate a different scaling and squaring algorithm proposed by Najfeld and Havel that employs a Padé approximation to the function x coth(x). This method is found to be essentially a variation of the standard one with weaker supporting error analysis. [ABSTRACT FROM AUTHOR]

The article contains numerical results, an extensive bibliography, and a detailed discussion of open problems. Topics discussed include the use of probabilistic ideas by applied mathematicians has seen a continued increase in recent decades, and probability appears frequently at modeling stage; and there is widespread interest in investigating the effects of noise and uncertainty; and probabilistic algorithms are routinely applied with much success to the solution of deterministic problems.

Computing the stationary distributions of a continuous-time Markov chain (CTMC) involves solving a set of linear equations. In most cases of interest, the number of equations is infinite or too large, and the equations cannot be solved analytically or numerically. Several approximation schemes overcome this issue by truncating the state space to a manageable size. In this review, we first give a comprehensive theoretical account of the stationary distributions and their relation to the long-term behaviour of CTMCs that is readily accessible to non-experts and free of irreducibility assumptions made in standard texts. We then review truncation-based approximation schemes for CTMCs with infinite state spaces paying particular attention to the schemes' convergence and the errors they introduce, and we illustrate their performance with an example of a stochastic reaction network of relevance in biology and chemistry. We conclude by elaborating on computational trade-offs associated with error control and several open questions. [ABSTRACT FROM AUTHOR]

We study the metric s--t path traveling salesman problem (TSP). An, Kleinberg, and Shmoys [Proceedings of the 44th ACM Symposium on Theory of Computing, 2012, pp. 875-886] improved on the long-standing 5/3 -approximation factor and presented an algorithm that achieves an approximation factor of 1+√5/2 ≈ 1.61803. Later, Sebö [Proceedings of the 16th Conference on Integer Programming and Combinatorial Optimization, 2013, pp. 362-374] further improved the approximation factor to 8/5. We present a simple, self-contained analysis that unifies both results; our main contribution is a unified correction vector. Additionally, we compare two different linear programming (LP) relaxations of the s--t path TSP, namely, the path version of the Held--Karp LP relaxation for the TSP and a weaker LP relaxation, and we show that both LPs have the same (fractional) optimal value. Also, we show that the minimum cost of integral solutions of the two LPs are within a factor of 3/2 of each other. Furthermore, we prove that a half-integral solution of the stronger LP relaxation of cost c can be rounded to an integral solution of cost at most 3/2 c. Finally, we give an example that presents obstructions to two natural methods that aim for an approximation factor of 3/2. [ABSTRACT FROM AUTHOR]

The symmetric eigenvalue decomposition and the singular value decomposition (SVD) are fundamental matrix decompositions with many applications. Conventional algorithms for computing these decompositions are suboptimal in view of recent trends in computer architectures which require minimizing communication together with arithmetic costs. Spectral divide-and-conquer algorithms, which recursively decouple the problem into two smaller subproblems, can achieve both requirements. Such algorithms can be constructed with the polar decomposition playing two key roles: it forms a bridge between the symmetric eigendecomposition and the SVD, and its connection to the matrix sign function naturally leads to spectral-decoupling. For computing the polar decomposition, the scaled Newton and QDWH iterations are two of the most popular algorithms, as they are backward stable and converge in at most nine and six iterations, respectively. Following this framework, we develop a higher-order variant of the QDWH iteration for the polar decomposition. The key idea of this algorithm comes from approximation theory: we use the best rational approximant for the scalar sign function due to Zolotarev in 1877. The algorithm exploits the extraordinary property enjoyed by the sign function that a high-degree Zolotarev function (best rational approximant) can be obtained by appropriately composing low-degree Zolotarev functions. This lets the algorithm converge in just two iterations in double-precision arithmetic, with the whopping rate of convergence seventeen. The resulting algorithms for the symmetric eigendecompositions and the SVD have higher arithmetic costs than the QDWH-based algorithms, but are better suited for parallel computing and exhibit excellent numerical backward stability. [ABSTRACT FROM AUTHOR]

In physics, it is sometimes desirable to compute the so-called density of states (DOS), also known as the spectral density, of a real symmetric matrix A. The spectral density can be viewed as a probability density distribution that measures the likelihood of finding eigenvalues near some point on the real line. The most straightforward way to obtain this density is to compute all eigenvalues of A, but this approach is generally costly and wasteful, especially for matrices of large dimension. There exist alternative methods that allow us to estimate the spectral density function at much lower cost. The major computational cost of these methods is in multiplying A with a number of vectors, which makes them appealing for large-scale problems where products of the matrix A with arbitrary vectors are relatively inexpensive. This article defines the problem of estimating the spectral density carefully and discusses how to measure the accuracy of an approximate spectral density. It then surveys a few known methods for estimating the spectral density and considers variations of existing methods. All methods are discussed from a numerical linear algebra point of view. [ABSTRACT FROM AUTHOR]

The amplitude of the gradient of a potential inside a wire cage is investigated, with particular attention to the 2D configuration of a ring of n disks of radius r held at equal potential. The Faraday shielding effect depends upon the wires having finite radius and is weaker than one might expect, scaling as |log r|/n in an appropriate regime of small r and large n. Both numerical results and a mathematical theorem are provided. By the method of multiple scales, a continuum approximation is then derived in the form of a homogenized boundary condition for the Laplace equation along a curve. The homogenized equation reveals that in a Faraday cage, charge moves so as to somewhat cancel an external field, but not enough for the cancellation to be fully effective. Physically, the effect is one of electrostatic induction in a surface of limited capacitance. An alternative discrete model of the effect is also derived based on a principle of energy minimization. Extensions to electromagnetic waves and 3D geometries are mentioned. [ABSTRACT FROM AUTHOR]

The method of multiple timescales is widely used in engineering and mathematical physics. In this article we draw attention to the literature on the comparison of various perturbation methods. We indicate where we can obtain an advantage from the concept of timescales, and we present examples where the anticipation of timescales makes sense and cases where, because of resonances or bifurcations, the analysis is less straightforward. In a number of problems second order approximations are essential to understand the phenomena. We will conclude from these examples that the anticipation of timescales as in the multiple timescales method may give misleading results; methods that do not anticipate timescales a priori such as averaging and renormalization should be used in research problems. [ABSTRACT FROM AUTHOR]

An introduction to the journal "Robust Padé Approximations via SVD" published in this issue of the journal is presented.

This article offers an accessible but rigorous and essentially self-contained account of some of the central ideas in compressed sensing, aimed at nonspecialists and undergraduates who have had linear algebra and some probability. The basic premise is first illustrated by considering the problem of detecting a few defective items in a large set. We then build up the mathematical framework of compressed sensing to show how combining efficient sampling methods with elementary ideas from linear algebra and a bit of approximation theory, optimization, and probability allows the estimation of unknown quantities with far less sampling of data than traditional methods. [ABSTRACT FROM AUTHOR]

We analyze globally convergent, derivative-free trust-region algorithms relying on radial basis function interpolation models. Our results extend the recent work of Conn, Scheinberg, and Vicente [SIAM J. Optim., 20 (2009), pp. 387-415] to fully linear models that have a nonlinear term. We characterize the types of radial basis functions that fit in our analysis and thus show global convergence to first-order critical points for the ORBIT algorithm of Wild, Regis, and Shoemaker [SIAM J. Sci. Comput., 30 (2008), pp. 3197-3219]. Using ORBIT, we present numerical results for different types of radial basis functions on a series of test problems. We also demonstrate the use of ORBIT in finding local minima on a computationally expensive environmental engineering problem involving remediation of contaminated groundwater. [ABSTRACT FROM AUTHOR]

When a function f(x) is holomorphic on an interval x ∈ [a, b], its roots on the interval can be computed by the following three-step procedure. First, approximate f(x) on [a, b] by a polynomial fN(x) using adaptive Chebyshev interpolation. Second, form the Chebyshev-Frobenius companion matrix whose elements are trivial functions of the Chebyshev coefficients of the interpolant fN(x). Third, compute all the eigenvalues of the companion matrix. The eigenvalues λ which lie on the real interval λ ∈ [a, b] are very accurate approximations to the zeros of f(x) on the target interval. (To minimize cost, the adaptive phase can automatically subdivide the interval, applying the Chebyshev rootfinder separately on each subinterval, to keep N bounded or to solve rare "dynamic range" complications.) We also discuss generalizations to compute roots on an infinite interval, zeros of functions singular on the interval [a, b], and slightly complex roots. The underlying ideas are undergraduate-friendly, but link the disparate fields of algebraic geometry, linear algebra, and approximation theory. [ABSTRACT FROM AUTHOR]

Padé approximation is considered from the point of view of robust methods of numerical linear algebra, in particular, the singular value decomposition. This leads to an algorithm for practical computation that bypasses most problems of solution of nearly-singular systems and spurious pole-zero pairs caused by rounding errors, for which a MATLAB code is provided. The success of this algorithm suggests that there might be variants of Pad#233; approximation that are pointwise convergent as the degrees of the numerator and denominator increase to ∞, unlike traditional Padé approximants, which converge only in measure or capacity. [ABSTRACT FROM AUTHOR]

The sparsity constrained rank-one matrix approximation problem is a difficult mathematical optimization problem which arises in a wide array of useful applications in engineering, machine learning, and statistics, and the design of algorithms for this problem has attracted intensive research activities. We introduce an algorithmic framework, called ConGradU, that unifies a variety of seemingly different algorithms that have been derived from disparate approaches, and that allows for deriving new schemes. Building on the old and well-known conditional gradient algorithm, ConGradU is a simplified version with unit step size that yields a generic algorithm which either is given by an analytic formula or requires a very low computational complexity. Mathematical properties are systematically developed and numerical experiments are given. [ABSTRACT FROM AUTHOR]

The article offers information on a study conducted by Sebastian Franz and Hans-Görg Roos about the behavior of numerical schemes when solving singularly perturbed problems. Singularly perturbed problems are a core topic in major graduate applied mathematics program since they are common in many application domains like circuit design and fluid dynamics. A discussion of more advanced layer-adaptive mesh schemes is also presented.

We review recent, developments of fast analytical methods for macroscopic electrostatic calculations in biological applications, including the Poisson-Boltzmann (PB) and the generalized Born models for electrostatic solvation energy. The focus is on analytical approaches for hybrid solvation models, especially the image charge method for a spherical cavity, and also the generalized Born theory as an approximation to the PB model. This review places much emphasis on the mathematical details behind these methods. [ABSTRACT FROM AUTHOR]

This work proposes and analyzes a stochastic collocation method for solving elliptic partial differential equations with random coefficients and forcing terms. These input data are assumed to depend on a finite number of random variables. The method consists of a Galerkin approximation in space and a collocation in the zeros of suitable tensor product orthogonal polynomials (Gauss points) in the probability space, and naturally leads to the solution of uncoupled deterministic problems as in the Monte Carlo approach. It treats easily a wide range of situations, such as input data that depend nonlinearly on the random variables, diffusivity coefficients with unbounded second moments, and random variables that are correlated or even unbounded. We provide a rigorous convergence analysis and demonstrate exponential convergence of the "probability error" with respect to the number of Gauss points in each direction of the probability space, under some regularity assumptions on the random input data. Numerical examples show the effectiveness of the method. Finally, we include a section with developments posterior to the original publication of this work. There we review sparse grid stochastic collocation methods, which are effective collocation strategies for problems that depend on a moderately large number of random variables. [ABSTRACT FROM AUTHOR]

Given a basic compact semialgebraic set K ᴄ ℝn, we introduce a methodology that generates a sequence converging to the volume of K. This sequence is obtained from optimal values of a hierarchy of either semidefinite or linear programs. Not only the volume but also every finite vector of moments of the probability measure that is uniformly distributed on K can be approximated as closely as desired, which permits the approximation of the integral on K of any given polynomial; the extension to integration against some weight functions is also provided. Finally, some numerical issues associated with the algorithms involved are briefly discussed. [ABSTRACT FROM AUTHOR]

We compare the convergence behavior of Gauss quadrature with that of its younger brother, Clenshaw-Curtis. Seven-line MATLAB codes are presented that implement both methods, and experiments show that the supposed factor-of-2 advantage of Gauss quadrature is rarely realized. Theorems are given to explain this effect. First, following O'Hara and Smith in the 1960s, the phenomenon is explained as a consequence of aliasing of coefficients in Chebyshev expansions. Then another explanation is offered based on the interpretation of a quadrature formula as a rational approximation of log((z + 1)/(z - 1)) in the complex plane. Gauss quadrature corresponds to Padé approximation at z = ∞. Clenshaw-Curtis quadrature corresponds to an approximation whose order of accuracy at z = ∞ is only half as high, but which is nevertheless equally accurate near [-1, 1]. [ABSTRACT FROM AUTHOR]

The problem of oscillatory polynomial interpolants arising from equally spaced mesh points is considered. It is shown that by making use of adaptive approaches the oscillations may be contained and the resulting polynomials are data-bounded and monotone on each interval. This is achieved at the cost of using a different polynomial on each subinterval. Computational results for a number of challenging functions including a number of problems similar to Runge's function with as many as 511 points per interval are shown. [ABSTRACT FROM AUTHOR]

Graph coloring has been employed since the 1980s to efficiently compute sparse Jacobian and Hessian matrices using either finite differences or automatic differentiation. Several coloring problems occur in this context, depending on whether the matrix is a Jacobian or a Hessian, and on the specifics of the computational techniques employed. We consider eight variant vertex coloring problems here. This article begins with a gentle introduction to the problem of computing a sparse Jacobian, followed by an overview of the historical development of the research area. Then we present a unifying framework for the graph models of the variant matrix estimation problems. The framework is based upon the viewpoint that a partition of a matrix into structurally orthogonal groups of columns corresponds to distance-2 coloring an appropriate graph representation. The unified framework helps integrate earlier work and leads to fresh insights; enables the design of more efficient algorithms for many problems; leads to new algorithms for others; and eases the task of building graph models for new problems. We report computational results on two of the coloring problems to support our claims. Most of the methods for these problems treat a column or a row of a matrix as an atomic entity, and partition the columns or rows (or both). A brief review of methods that do not fit these criteria is provided. We also discuss results in discrete mathematics and theoretical computer science that intersect with the topics considered here. [ABSTRACT FROM AUTHOR]

Focuses on a study which presented a fully polynomial randomized approximation scheme for the classic all-terminal network reliability problem. Information on the basic FPRAS for FAIL; Details on the Monte Carlo simulation for estimating FAIL; Conclusion.

An introduction to the article "Finding the Zeros of a Univariate Equation: Proxy Rootfinders, Chebyshev Interpolation, and the Companion Matrix," by John Boyd is presented.