Hit-and-run algorithms for the identification of nonredundant linear inequalities

Two probabilistic hit-and-run algorithms are presented to detect nonredundant constraints in a full dimensional system of linear inequalities. The algorithms proceed by generating a random sequence of interior points whose limiting distribution is uniform, and by searching for a nonredundant constraint in the direction of a random vector from each point in the sequence. In the hypersphere directions algorithm the direction vector is drawn from a uniform distribution on a hypersphere. In the computationally superior coordinate directions algorithm a search is carried out along one of the coordinate vectors. The algorithms are terminated through the use of a Bayesian stopping rule. Computational experience with the algorithms and the stopping rule will be reported.     

A shuffle that mixes sets of any fixed size much faster than it mixes the whole deck

Consider an n by n array of cards shufled in the following manner. An element x of the array is chosen uniformly at random. Then with probability 1/2 the rectangle of cards above and to the left of x is rotated 180deg;, and with probability 1/2 the rectangle of cards below and to the right of x is rotated 180°. It is shown by an eigenvalue method that the time required to approach- the uniform distribution is between n²/2 and cn² in n for some constant c. On the other hand, for any k it is shown that the time needed to uniformly distribute a set of cards of size k is at most c(k)n, where c(k) is a constant times k³ In(k)². This is established via coupling; no attempt is made to get a good constant. © 1994 John Wiley & Sons, Inc.     

Random walk on upper triangular matrices mixes rapidly

We present an upper bound O(n ² ) for the mixing time of a simple random walk on upper triangular matrices. We show that this bound is sharp up to a constant, and find tight bounds on the eigenvalue gap. We conclude by applying our results to indicate that the asymmetric exclusion process on a circle indeed mixes more rapidly than the corresponding symmetric process. Received: 25 January 1999 / Revised version: 17 September 1999 / Published online: 14 June 2000     

The fast Slepian transform

The discrete prolate spheroidal sequences (DPSS's) provide an efficient representation for discrete signals that are perfectly timelimited and nearly bandlimited. Due to the high computational complexity of projecting onto the DPSS basis – also known as the Slepian basis – this representation is often overlooked in favor of the fast Fourier transform (FFT). We show that there exist fast constructions for computing approximate projections onto the leading Slepian basis elements. The complexity of the resulting algorithms is comparable to the FFT, and scales favorably as the quality of the desired approximation is increased. In the process of bounding the complexity of these algorithms, we also establish new nonasymptotic results on the eigenvalue distribution of discrete time–frequency localization operators. We then demonstrate how these algorithms allow us to efficiently compute the solution to certain least-squares problems that arise in signal processing. We also provide simulations comparing these fast, approximate Slepian methods to exact Slepian methods as well as the traditional FFT based methods.     

The fast quartic solver

A fast and highly accurate algorithm for solving quartic equations is introduced. This new algorithm is more than six times as fast and several times more accurate than the quasi-standard Companion matrix eigenvalue quartic solver. Moreover, the method is exceptionally robust in cases of extreme root spread. The new algorithm is based on a factorization of the quartic in two quadratics, which are solved in closed form. The performance key at this point is a fixed-point iteration based fitting algorithm for backward optimization of the underlying quartic-to-quadratic polynomial decomposition. Detailed experimental results confirm our claims.     

A fast Poisson solver

Summary A direct method is developed for the discrete solution of Poisson's equation on a rectangle. The algorithm proposed is of the class of marching methods. The idea is to generalize the classical Cramer's method using Chebyshev matrix polynomials formalism. This results in the solution ofN independent diagonal system of linear equations in the eigenvector coordinate system. An elementary transformation to the original coordinate system is then carried out.     

Generalized fast automatic differentiation technique

A new efficient technique intended for the numerical solution of a broad class of optimal control problems for complicated dynamical systems described by ordinary and/or partial differential equations is investigated. In this approach, canonical formulas are derived to precisely calculate the objective function gradient for a chosen finite-dimensional approximation of the objective functional.     

A fast compactifying garbage collector

A compactifying garbage collection algorithm is described which surpasses previously published comparable algorithms. A proof of the algorithm is given although details are omitted. The task of proving programs of realistic complexity is discussed.     

Plethysm and fast matrix multiplication

Motivated by the symmetric version of matrix multiplication we study the plethysm $S^k({\mathfrak{sl}}_n)$ of the adjoint representation ${\mathfrak{sl}}_n$ of the Lie group $S{L}_n$. In particular, we describe the decomposition of this representation into irreducible components for $k=3$, and find highest-weight vectors for all irreducible components. Relations to fast matrix multiplication, in particular the Coppersmith–Winograd tensor, are presented.     

Efficient fast marching with Finsler metrics

We study the discretization of the escape time problem: find the length of the shortest path joining an arbitrary point $z$ of a domain $\Omega $ , to the boundary $\partial \Omega $ . Path length is measured locally via a Finsler metric, potentially asymmetric and strongly anisotropic. This optimal control problem can be reformulated as a static Hamilton–Jacobi partial differential equation, or as a front propagation model. It has numerous applications, ranging from motion planning to image segmentation. We introduce a new algorithm, fast marching using anisotropic stencil refinement (FM-ASR), which addresses this problem on a two dimensional domain discretized on a cartesian grid. The local stencils used in our discretization are produced by arithmetic means, like in the FM-LBR (Mirebeau in Anisotropic fast Marching on Cartesian grids, using lattice basis reduction, preprint 2012), a method previously introduced by the author in the special case of Riemannian metrics. The complexity of the FM-ASR, in an average sense over all grid orientations, only depends (poly-)logarithmically on the anisotropy ratio of the metric, while most alternative approaches have a polynomial dependence. Numerical experiments show, in several occasions, that the accuracy/complexity compromise is improved by an order of magnitude or more.     

A fast algorithm for balanced sampling

Summary  The cube method (Deville & Tillé 2004) is a large family of algorithms that allows selecting balanced samples with equal or unequal inclusion probabilities. In this paper, we propose a very fast implementation of the cube method. The execution time does not depend on the square of the population size anymore, but only on the population size. Balanced samples can thus be selected in very large populations of several hundreds of thousands of units.     

A fast Poisson solver on disks

We present a fast/parallel Poisson solver on disks, based on efficient evaluation of the exact solution given by the Newtonian potential and the Poisson integral. Derived from an integral formulation, it is more accurate and simpler in parallel implementation and in upgrading to a higher order algorithm, than an algorithm which solves the linear system obtained from a differential formulation.     

A fast algorithm for image registration

An algorithm is presented here to estimate a smooth motion at a high frame rate. It is derived from the non-linear constant brightness assumption. A hierarchical approach reduces the dimension of the space of admissible displacements, hence the number of unknown parameters is small compared to the size of the data. The optimal displacement is estimated by a Gauss–Newton method, and the matrix required at each step is assembled rapidly using a finite-element method. To cite this article: J. Fehrenbach, M. Masmoudi, C. R. Acad. Sci. Paris, Ser. I 346 (2008).     

A simple fast hybrid pattern-matching algorithm

The Knuth–Morris–Pratt (KMP) pattern-matching algorithm guarantees both independence from alphabet size and worst-case execution time linear in the pattern length; on the other hand, the Boyer–Moore (BM) algorithm provides near-optimal average-case and best-case behaviour, as well as executing very fast in practice. We describe a simple algorithm that employs the main ideas of KMP and BM (with a little help from Sunday) in an effort to combine these desirable features. Experiments indicate that in practice the new algorithm is among the fastest exact pattern-matching algorithms discovered to date, apparently dominant for alphabet size above 15–20.     

Regularized fast multiple-image deconvolution for LBT

In this paper we study a fast deconvolution technique for the image restoration problem of the Large Binocular Telescope (LBT) interferometer. Since LBT provides several blurred and noisy images of the same object, it requires the use of multiple-image deconvolution methods in order to produce a unique image with high resolution. Hence the restoration process is basically a linear ill-posed problem, with overdetermined system and data corrupted by several components of noise.     

A fast wavelet block Jacobi method

In this paper, we develop a fast block Jacobi method for linear systems based on discrete wavelet transform (DWT). Traditional wavelet-based methods for linear systems do not fully utilize the sparsity and the multi-level block structure of the transformed matrix after DWT. For the sake of numerical efficiency, we truncate the transformed matrix to be a sparse matrix by letting the small values be zero. To combine the advantages of the direct method and the iterative method, we solve the sub-systems appropriately based on the multi-level block structure of the transformed matrix after DWT. Numerical examples show that the proposed method is very numerically effective.