Fast computation of adaptive wavelet expansions

In this paper we describe and analyze an algorithm for the fast computation of sparse wavelet coefficient arrays typically arising in adaptive wavelet solvers. The scheme improves on an earlier version from Dahmen et al. (Numer. Math. 86, 49–101, 2000) in several respects motivated by recent developments of adaptive wavelet schemes. The new structure of the scheme is shown to enhance its performance while a completely different approach to the error analysis accommodates the needs put forward by the above mentioned context of adaptive solvers. The results are illustrated by numerical experiments for one and two dimensional examples.     

Fast computation of convolution operations via low-rank approximation

Methods for the approximation of 2D discrete convolution operations are derived for the case when a low-rank approximation of one of the input matrices is available. Algorithms based on explicit computation of discrete convolution and on the Fast Fourier Transform are both described. Applications of the described methods to the computation of cross-correlation and autocorrelation are discussed and illustrated by examples. Both theory and numerical experiments show that the use of low-rank approximations makes it possible to determine accurate approximations of convolution, cross-correlation, and autocorrelation operations at competitive speeds.     

When polynomial approximation meets exact computation

We outline a relatively new research agenda aiming at building a new approximation paradigm by matching two distinct domains, the polynomial approximation and the exact solution of NP -hard problems by algorithms with guaranteed and non-trivial upper complexity bounds. We show how one can design approximation algorithms achieving ratios that are “forbidden” in polynomial time (unless a very unlikely complexity conjecture is confirmed) with worst-case complexity much lower than that of an exact computation.     

Fast computation of spectral centroids

The spectral centroid of a signal is the curve whose value at any given time is the centroid of the corresponding constant-time cross section of the signal’s spectrogram. A spectral centroid provides a noise-robust estimate of how the dominant frequency of a signal changes over time. As such, spectral centroids are an increasingly popular tool in several signal processing applications, such as speech processing. We provide a new, fast and accurate algorithm for the real-time computation of the spectral centroid of a discrete-time signal. In particular, by exploiting discrete Fourier transforms, we show how one can compute the spectral centroid of a signal without ever needing to explicitly compute the signal’s spectrogram. We then apply spectral centroids to an emerging biometrics problem: to determine a person’s heart and breath rates by measuring the Doppler shifts their body movements induce in a continuous wave radar signal. We apply our algorithm to real-world radar data, obtaining heart- and breath-rate estimates that compare well against ground truth.     

Matrix valued adaptive cross approximation

A new variant of the Adaptive Cross Approximation (ACA) for approximation of dense block matrices is presented. This algorithm can be applied to matrices arising from the Boundary Element Methods (BEM) for elliptic or Maxwell systems of partial differential equations. The usual interpolation property of the ACA is generalised for the matrix valued case. Some numerical examples demonstrate the efficiency of the new method. The main example will be the electromagnetic scattering problem, that is, the exterior boundary value problem for the Maxwell system. Here, we will show that the matrix valued ACA method works well for high order BEM, and the corresponding high rate of convergence is preserved. Another example shows the efficiency of the new method in comparison with the standard technique, whilst approximating the smoothed version of the matrix valued fundamental solution of the time harmonic Maxwell system. Copyright © 2016 John Wiley & Sons, Ltd.     

Fast computation of two-level circulant preconditioners

In this paper we present an algorithm for the construction of the superoptimal circulant preconditioner for a two-level Toeplitz linear system. The algorithm is fast, in the sense that it operates in FFT time. Numerical results are given to assess its performance when applied to the solution of two-level Toeplitz systems by the conjugate gradient method, compared with the Strang and optimal circulant preconditioners.     

Fast computation of generic bivariate resultants

We prove that the resultant of two “sufficiently generic” bivariate polynomials over a finite field can be computed in quasi-linear expected time, using a randomized algorithm of Las Vegas type. A similar complexity bound is proved for the computation of the lexicographical Gröbner basis for the ideal generated by the two polynomials.     

Exponential convergence of adaptive quarklet approximation

This paper is concerned with approximation properties of polynomially enriched wavelet systems, so-called quarklet frames. We show that certain model singularities that arise in elliptic boundary value problems on polygonal domains can be approximated from the span of such quarklet systems at inverse-exponential rates. In order to realize these, we combine spatial refinement in the vicinity of the singularities with suitable growth of the polynomial degrees in regions where the solution is smooth, similar to adaptive hp-finite element approximation.     

Fast one-sided approximation with spline functions

For the approximation of functions, interpolation compromises approximation error for computational convenience. For a bounded interpolation operator the Lebesque inequality bounds the factor by which the interpolation differs from the best approximation available in the range of the operator. A comparable process for one-sided approximation is not readily apparent. Methods are suggested for the computationally economical construction of one-sided spline approximation to large classes of functions, and criteria for comparing such approximation operators are investigated. Since the operators are generally nonlinear the Lebesque inequality is invalidated as an aid for comparing with the best one-sided approximation in the range of the operator, but comparable inequalities are shown to exist in some cases.     

Fast computation of the modality of polygons

The modality of a vertex of a polygon is the number of minima or maxima in the distance function from the vertex under consideration to each of the other vertices taken in order around the polygon. Modality was defined by Avis, Toussaint, and Bhattacharya (Comput. Math Appl., 8 (1982), 153–156) and has been further studied by Toussaint and Bhattacharya (Technical Report, No. SOCS-81.3, School of Computer Science, McGill University, January 1981). These authors have defined modality for polygons, both convex and nonconvex, but have not given an algorithm to compute the modality of a polygon, other than the obvious algorithm derived from the definition, which is quadratic in the number of vertices of the polygon. Our paper gives a modality-determination algorithm for convex polygons whose running time is linear in the sum of the number of vertices and the total modality of the polygon. As a special case, we can test if a convex polygon is unimodal (a term introduced by Avis et al.) in time O(n) for a polygon with n vertices. This latter result is shown to be optimal to within a constant factor. We then extend our technique to nonconvex polygons and derive a modality-determination algorithm which is better than the obvious algorithm, but probably not optimal. We conclude by posing some open problems and indicating a connection between modality determination and a range query problem which has received some attention in the Computational Geometry literature.     

A note on adaptive approximation in Sobolev spaces

In this article, we consider the adaptive approximation in Sobolev spaces. After establishing some norm equivalences and inequalities in Besov spaces, we are able to prove that the best N terms approximation with wavelet‐like basis in Sobolev spaces exhibits the proper approximation order in terms of N^?1. This indicates that the computational load in adaptive approximation is proportional to the approximation accuracy. © 2006 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2007     

On approximation of dominating tree in wireless sensor networks

We study the following problem: Given a weighted graph G = (V, E, w) with \({w: E \rightarrow \mathbb{Z}^+}\) , the dominating tree (DT) problem asks us to find a minimum total edge weight tree T such that for every \({v \in V}\) , v is either in T or adjacent to a vertex in T. To the best of our knowledge, this problem has not been addressed in the literature. Solving the DT problem can yield a routing backbone for broadcast protocols since (1) each node does not have to construct their own broadcast tree, (2) utilize the virtual backbone to reduce the message overhead, and (3) the weight of backbone representing the energy consumption is minimized. We prove the hardness of this problem, including the inapproximability result and present an approximation algorithm together with an efficient heuristic. Finally, we verify the effectiveness of our proposal through simulation.     

Fast approximation of matroid packing and covering

We study packing problems with matroid structures, which includes the strength of a graph of Cunningham and scheduling problems. If \(\mathcal {M}\) is a matroid over a set of elements S with independent set \(\mathcal {I}\), and \(m=|S|\), we suppose that we are given an oracle function that takes an independent set \(A\in \mathcal {I}\) and an element \(e\in S\) and determines if \(A\cup \{e\}\) is independent in time I(m). Also, given that the elements of A are represented in an ordered way \(A=\{A_1,\dots ,A_k\}\), we denote the time to check if \(A\cup \{e\}\notin \mathcal {I}\) and if so, to find the minimum \(i\in \{0,\dots ,k\}\) such that \(\{A_1,\dots ,A_i\}\cup \{e\}\notin \mathcal {I}\) by \(I^*(m)\). Then, we describe a new FPTAS that computes for any \(\varepsilon >0\) and for any matroid \(\mathcal {M}\) of rank r over a set S of m elements, in memory space O(m), the packing \(\varLambda ({\mathcal {M}})\) within \(1+\varepsilon \) in time \(O(mI^*(m)\log (m)\log (m/r)/\varepsilon ^2)\), and the covering \(\varUpsilon ({\mathcal {M}})\) in time \(O(r\varUpsilon ({\mathcal {M}})I(m)\log (m)\log (m/r)/\varepsilon ^2)\). This method outperforms in time complexity by a factor of \(\varOmega (m/r)\) the FPTAS of Plotkin, Shmoys, and Tardos, and a factor of \(\varOmega (m)\) the FPTAS of Garg and Konemann. On top of the value of the packing and the covering, our algorithm exhibits a combinatorial object that proves the approximation. The applications of this result include graph partitioning, minimum cuts, VLSI computing, job scheduling and others.     

Automatic approximation using asymptotically optimal adaptive interpolation

Numerical Algorithms - We present an asymptotic analysis of adaptive methods for Lp approximation of functions f ∈ Cr([a, b]), where $1le ple +infty $ . The methods rely on piecewise...     

Fast Runge-Kutta approximation of inhomogeneous parabolic equations

The result after N steps of an implicit Runge-Kutta time discretization of an inhomogeneous linear parabolic differential equation is computed, up to accuracy ɛ, by solving only linear systems of equations. We derive, analyse, and numerically illustrate this fast algorithm.     

Fast Moreau envelope computation I: numerical algorithms

The present article summarizes the state of the art algorithms to compute the discrete Moreau envelope, and presents a new linear-time algorithm, named NEP for NonExpansive Proximal mapping. Numerical comparisons between the NEP and two existing algorithms: The Linear-time Legendre Transform (LLT) and the Parabolic Envelope (PE) algorithms are performed. Worst-case time complexity, convergence results, and examples are included. The fast Moreau envelope algorithms first factor the Moreau envelope as several one-dimensional transforms and then reduce the brute force quadratic worst-case time complexity to linear time by using either the equivalence with Fast Legendre Transform algorithms, the computation of a lower envelope of parabolas, or, in the convex case, the non expansiveness of the proximal mapping.      

Absolute and relative cut-off in adaptive approximation by wavelets

Given the wavelet expansion of a function v, a non-linear adaptive approximation of v is obtained by neglecting those coefficients whose size drops below a certain threshold. We propose several ways to define the threshold: all are based on the characterization of the local regularity of v (in a Sobolev or Besov scale) in terms of summability of properly defined subsets of its coefficients. A-priori estimates of the approximation error are derived. For the Haar system the asymptotic behavior of both the approximation error and the number of survived coefficients is thoroughly investigated for a class of functions having Hölder-type singularities.     

Fast computation of bounds for two-terminal network reliability

In this paper, an algorithm for the fast computation of network reliability bounds is proposed. The evaluation of the network reliability is an intractable problem for very large networks, and hence approximate solutions based on reliability bounds have assumed importance. The proposed bounds computation algorithm is based on an efficient BDD representation of the reliability graph model and a novel search technique to find important minpaths/mincuts to quickly reduce the gap between the reliability upper and lower bounds. Furthermore, our algorithm allows the control of the gap between the two bounds by controlling the overall execution time. Therefore, a trade-off between prediction accuracy and computational resources can be easily made in our approach. The numerical results are presented for large real example reliability graphs to show the efficacy of our approach.