Fast inputs in the problem of control synthesis under uncertainty

We present a class of bounded control inputs that permits one to solve target control synthesis problems for linear systems with geometric (“instantaneous”) constraints on the perturbations by reduction to simpler programmed control problems.     

Fast data extrapolating

Data-extrapolating (extension) technique has important applications in image processing on implicit surfaces and in level set methods. The existing data-extrapolating techniques are inefficient because they are designed without concerning the specialities of the extrapolating equations. Besides, there exists little work on locating the narrow band after data extrapolating—a very important problem in narrow band level set methods. In this paper, we put forward the general Huygens’ principle, and based on the principle we present two efficient data-extrapolating algorithms. The algorithms can easily locate the narrow band in data extrapolating. Furthermore, we propose a prediction–correction version for the data-extrapolating algorithms and the corresponding band locating method for a special case where the direct band locating method is hard to apply. Experiments demonstrate the efficiency of our algorithms and the convenience of the band locating method.     

Fast positive operatoren

Ohne Zusammenfassung     

Fast Fourier optimization

Many interesting and fundamentally practical optimization problems, ranging from optics, to signal processing, to radar and acoustics, involve constraints on the Fourier transform of a function. It is well-known that the fast Fourier transform (fft) is a recursive algorithm that can dramatically improve the efficiency for computing the discrete Fourier transform. However, because it is recursive, it is difficult to embed into a linear optimization problem. In this paper, we explain the main idea behind the fast Fourier transform and show how to adapt it in such a manner as to make it encodable as constraints in an optimization problem. We demonstrate a real-world problem from the field of high-contrast imaging. On this problem, dramatic improvements are translated to an ability to solve problems with a much finer grid of discretized points. As we shall show, in general, the “fast Fourier” version of the optimization constraints produces a larger but sparser constraint matrix and therefore one can think of the fast Fourier transform as a method of sparsifying the constraints in an optimization problem, which is usually a good thing.     

Fast Thermoviscous Convection

This paper studies the asymptotic structure of convection in an infinite Prandtl number fluid with strongly temperature-dependent viscosity, in the limit where the dimensionless activation energy 1/ε is large, and the Rayleigh number R, defined (essentially) with the basal viscosity and the prescribed temperature drop, is also large. We find that the Nusselt number N is given by N~CεR^1/5, where C depends on the aspect ratio a. The relative error in this result is O(R^?1/10ε^?1/4, ε^1/2, R^?2/5ε^?2, R^?2/20ε^?1/24), so that we cannot hope to find accurate confirmation of this result at moderate Rayleigh numbers, though it should serve as a useful indicator of the relative importance of R and ε. For the above result to be valid, we require R ? 1/ε⁵ ?1. More important, however, is the asymptotic structure of the flow: there is a cold (hence rigid) lid with sloping base, beneath which a rapid, essentially isoviscous, convection takes place. This convection is driven by plumes at the sides, which generate vorticity due to thermal buoyancy, as in the constant viscosity case (Roberts, 1979). However, the slope of the lid base is sufficient to cause a large shear stress to be generated in the thermal boundary layer which joins the lid to the isoviscous region underneath (though a large velocity is not generated); consequently, the layer does not “see” the shear stress exerted by the interior flow (at leading order), and therefore the thermal boundary layer structure is totally self-determined: it even has a similarity structure (as a consequence). This fact makes it easy to analyse the problem, since the boundary layer uncouples from the rest of the flow. In addition, we find an alternative scaling (in which the lid base is “almost” flat), but it seems that the resulting boundary layer equations have no solution, though this is certainly open to debate: the results quoted above are not for this case. When a free slip boundary condition is applied at the top surface, one finds that there exists a thin “skin” at the top of the lid which is a stress boundary layer. The shear stress changes rapidly to zero, and there exists a huge longitudinal stress (compressive/tensile) in this skin. For earthlike parameters, this stress far exceeds the fracture strength of silicate rocks.     

Fast decreasing polynomials

Matching two-sided estimates are given for the minimal degree of polynomialsP satisfyingP(0)=1 and ¦P(x)|exp(– (¦x¦)),x [–1,1], where is an arbitrary, in [0, 1], increasing function. Besides these fast decreasing polynomials we also consider bell-shaped polynomials and polynomials approximating well the signum function.Communicated by Edward B. Saff.     

Fast decreasing rational functions

Necessary and sufficient conditions are obtained for the existence of sequences of rational functions of the formr _n(x) =p _n(x)/p_n(−x), withp _n a polynomial of degreen, that decrease geometrically on (0, 1] in accordance with a specified rate function. The technique of proof involves minimum energy problems for Green potentials in the presence of an external field. Applications are given for the construction of rational approximations of |x| and sgn(x) on [−1, 1] having geometric rates of convergence forx ≠ 0. The research of this author was supported, in part, by National Science Foundation grant DMS-9501130.     

Penalized Fast Subset Scanning

We present the penalized fast subset scan (PFSS), a new and general framework for scalable and accurate pattern detection. PFSS enables exact and efficient identification of the most anomalous subsets of the data, as measured by a likelihood ratio scan statistic. However, PFSS also allows incorporation of prior information about each data element’s probability of inclusion, which was not previously possible within the subset scan framework. PFSS builds on two main results: first, we prove that a large class of likelihood ratio statistics satisfy a property that allows additional, element-specific penalty terms to be included while maintaining efficient computation. Second, we prove that the penalized statistic can be maximized exactly by evaluating only O(N) subsets. As a concrete example of the PFSS framework, we incorporate “soft” constraints on spatial proximity into the spatial event detection task, enabling more accurate detection of irregularly shaped spatial clusters of varying sparsity. To do so, we develop a distance-based penalty function that rewards spatial compactness and penalizes spatially dispersed clusters. This approach was evaluated on the task of detecting simulated anthrax bio-attacks, using real-world Emergency Department data from a major U.S. city. PFSS demonstrated increased detection power and spatial accuracy as compared to competing methods while maintaining efficient computation.     

Fast block Toeplitz orthogonalization

Summary Algorithms are presented which compute theQR factorization of a block-Toeplitz matrix inO(n) ² block-operations, wheren is the block-order of the matrix and a block-operation is a multiplication, inversion or a set of Householder operations involving one or two blocks. The algorithms are in general analogous to those presented in the scalar Toeplitz case in a previous paper, but the basic operation is the Householder transform rather than the Givens transform, and the computation of the Householder coefficients and other working matrices requires special treatment. Two algorithms are presented-the first computes onlyR explicitly and the second computes bothQ andR.     

Fast Deterministic Processor Allocation

Interval allocation has been suggested as a possible formalization for the PRAM of the (vaguely defined) processor allocation problem, which is of fundamental importance in parallel computing. The interval allocation problem is, given n nonnegative integers x₁, . . ., x_n, to allocate n nonoverlapping subarrays of sizes x₁, . . ., x_n from within a base array of O(Σⁿ_j=1x_j) cells. We show that interval allocation problems of size n can be solved in O((log log n)³) time with optimal speedup on a deterministic CRCW PRAM. In addition to a general solution to the processor allocation problem, this implies an improved deterministic algorithm for the problem of approximate summation. For both interval allocation and approximate summation, the fastest previous deterministic algorithms have running times of Θ(log n/log log n). We describe an application to the problem of computing the connected components of an undirected graph. Finally we show that there is a nonuniform deterministic algorithm that solves interval allocation problems of size n in O(log log n) time with optimal speedup.     

Fast generation of cubic graphs

In this paper an efficient algorithm to generate regular graphs with small vertex valency is presented. The running times of a program based on this algorithm and designed to generate cubic graphs are below two natural benchmarks: (a) If N(n) denotes the number of pairwise non-isomorphic cubic graphs with n vertices and T(n) the time needed for generating the list of all these graphs, then T(n)/N(n) decreases gradually for the observed values of n. This suggests that T(n)/N(n) might be uniformly bounded for all n, ignoring the time to write the outputs, but we are unable to prove this and in fact are not confident about it. (b) For programs that generate lists of non-isomorphic objects, but cannot a priori make sure to avoid the generation of isomorphic copies, the time needed to check a randomly ordered list of these objects for being non-isomorphic is a natural benchmark. Since for large lists (n ≥ 22, girth 3) existing graph isomorphism programs take longer to canonically label all of the N(n) graphs than our algorithm takes to generate them, our algorithm is probably faster than any method which does one or more isomorphism test for every graph. © 1996 John Wiley & Sons, Inc.     

Fast decoding of Gabidulin codes

Gabidulin codes are the analogues of Reed–Solomon codes in rank metric and play an important role in various applications. In this contribution, a method for efficient decoding of Gabidulin codes up to their error correcting capability is shown. The new decoding algorithm for Gabidulin codes (defined over ${\mathbb{F}_{q^m}}$ ) directly provides the evaluation polynomial of the transmitted codeword. This approach can be seen as a Gao-like algorithm and uses an equivalent of the Euclidean Algorithm. In order to achieve low complexity, a fast symbolic product and a fast symbolic division are presented. The complexity of the whole decoding algorithm for Gabidulin codes is ${\mathcal{O} (m^3 \, \log \, m)}$ operations over the ground field ${\mathbb{F}_q}$ .     

Fast pattern-matching on indeterminate strings

In a string x on an alphabet Σ, a position i is said to be indeterminate iff x[i] may be any one of a specified subset {λ₁,λ₂,…,λ_j} of Σ, 2j|Σ|. A string x containing indeterminate positions is therefore also said to be indeterminate. Indeterminate strings can arise in DNA and amino acid sequences as well as in cryptological applications and the analysis of musical texts. In this paper we describe fast algorithms for finding all occurrences of a pattern p=p[1..m] in a given text x=x[1..n], where either or both of p and x can be indeterminate. Our algorithms are based on the Sunday variant of the Boyer–Moore pattern-matching algorithm, one of the fastest exact pattern-matching algorithms known. The methodology we describe applies more generally to all variants of Boyer–Moore (such as Horspool's, for example) that depend only on calculation of the δ (“rightmost shift”) array: our method therefore assumes that Σ is indexed (essentially, an integer alphabet), a requirement normally satisfied in practice.     

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.     

Fast algorithms for greedy triangulation

We present the first quadratic-time algorithm for the greedy triangulation of a finite planar point set, and the first linear-time algorithm for the greedy triangulation of a convex polygon.     

Fast Fourier wavelet packet transformation

The wavelet basis generated by Shannon's sampling theorem is presented. Periodical finite dimensional wavelet and Fourier wavelet packets are suggested. A link of constructed bases with complex trigonometric series and discrete Fourier transformation is considered. The Fourier wavelet packet may be used as widely as discrete Fourier transformation. Vilnius University, Naugarduko 24, 2006 Vilnius, Lithuania. Published in Lietuvos Matematikos Rinkinys, Vol. 34, No. 4, pp. 411–433, October–December, 1994.     

Fast Construction of Optimal Circulant Preconditioners for Matrices from the Fast Dense Matrix Method

In this paper, we consider solving non-convolution type integral equations by the preconditioned conjugate gradient method. The fast dense matrix method is a fast multiplication scheme that provides a dense discretization matrix A approximating a given integral equation. The dense matrix A can be constructed in O(n) operations and requires only O(n) storage where n is the size of the matrix. Moreover, the matrix-vector multiplication A xcan be done in O(n log n) operations. Thus if the conjugate gradient method is used to solve the discretized system, the cost per iteration is O(n log n) operations. However, for some integral equations, such as the Fredholm integral equations of the first kind, the system will be ill-conditioned and therefore the convergence rate of the method will be slow. In these cases, preconditioning is required to speed up the convergence rate of the method. A good choice of preconditioner is the optimal circulant preconditioner which is the minimizer of C – A _F in Frobenius norm over all circulant matrices C. It can be obtained by taking arithmetic averages of all the entries of A and therefore the cost of constructing the preconditioner is of O(n ²) operations for general dense matrices. In this paper, we develop an O(n log n) method of constructing the preconditioner for dense matrices A obtained from the fast dense matrix method. Application of these ideas to boundary integral equations from potential theory will be given. These equations are ill-conditioned whereas their optimal circulant preconditioned equations will be well-conditioned. The accuracy of the approximation A, the fast construction of the preconditioner and the fast convergence of the preconditioned systems will be illustrated by numerical examples.