A fast algorithm for solving systems of linear equations with two variables per equation

We present a fast algorithm for solving m X n systems of linear equations Ax = c with at most two variables per equation. The algorithm makes use of a linear-time algorithm for constructing a spanning forest of an undirected graph, and it requires 5m + 2n – 2 arithmetic operations in the worst case.     

A computational method for the indefinite quadratic programming problem

We present an algorithm for the quadratic programming problem of determining a local minimum of ?(x)=$\text{1}\text{2}$x^TQx+c^Tx such that A^Tx?b where Q ymmetric matrix which may not be positive definite. Our method combines the active constraint strategy of Murray with the Bunch-Kaufman algorithm for the stable decomposition of a symmetric matrix. Under the active constraint strategy one solves a sequence of equality constrained problems, the equality constraints being chosen from the inequality constraints defining the original problem. The sequence is chosen so that ?(x) continues to decrease and x remains feasible. Each equality constrained subproblem requires the solution of a linear system with the projected Hessian matrix, which is symmetric but not necessarily positive definite. The Bunch-Kaufman algorithm computes a decomposition which facilitates the stable determination of the solution to the linear system. The heart of this paper is a set of algorithms for updating the decomposition as the method progresses through the sequence of equality constrained problems. The algorithm has been implemented in a FORTRAN program, and a numerical example is given.     

Shifted tableaux,schur Q-functions,and a conjecture of R. Stanley

We present an analog of the Robinson-Schensted correspondence that applies to shifted Young tableaux and is considerably simpler than the one proposed in [B. E. Sagan, J. Combin. Theory Ser. A 27 (1979), 10–18]. In addition, this algorithm enjoys many of the important properties of the original Robinson-Schensted map including an interpretation of row lengths in terms of k-increasing sequences, a jeu de taquin, and a generalization to tableaux with repeated entries analogous to Knuth's construction (Pacific J. Math. 34 (1970), 709–727). The fact that the Knuth relations hold for our algorithm yields a simple proof of a conjecture of Stanley.     

Factoring Polynomials over Special Finite Fields

We exhibit a deterministic algorithm for factoring polynomials in one variable over finite fields. It is efficient only if a positive integer k is known for which Φ_k(p) is built up from small prime factors; here Φ_k denotes the kth cyclotomic polynomial, and p is the characteristic of the field. In the case k=1, when Φ_k(p)=p−1, such an algorithm was known, and its analysis required the generalized Riemann hypothesis. Our algorithm depends on a similar, but weaker, assumption; specifically, the algorithm requires the availability of an irreducible polynomial of degree r over Z/pZ for each prime number r for which Φ_k(p) has a prime factor l with l≡1 mod r. An auxiliary procedure is devoted to the construction of roots of unity by means of Gauss sums. We do not claim that our algorithm has any practical value.     

Numerical solution of the Monge–Ampère equation by a Newton's algorithm

We solve numerically the Monge–Ampère equation with periodic boundary condition using a Newton's algorithm. We prove convergence of the algorithm, and present some numerical examples, for which a good approximation is obtained in 10 iterations. To cite this article: G. Loeper, F. Rapetti, C. R. Acad. Sci. Paris, Ser. I 340 (2005).     

Sur la reconstruction des polynômes linéaires : un nouvel algorithme de décodage des codes de Gabidulin

We describe a reconstruction problem for linearized polynomials. We equally describe a polynomial-time algorithm enabling to solve this problem in a simple case. From this algorithm we deduce an alternative efficient decoding algorithm for Gabidulin codes introduced in 1985. To cite this article: P. Loidreau, C. R. Acad. Sci. Paris, Ser. I 339 (2004).     

Consistency of Landweber algorithm in an ill-posed problem with random data

This Note deals with the linear ill-posed problem, described by operator equations in which the second member is measured with random errors. We first show the existence and the unicity of the pseudo-solution for such a problem and later estimate it using Landweber algorithm. We also show the ‘almost complete convergence’ (a.co) of this algorithm specifying its convergence rate. We finally build a confidence domain for the so mentioned pseudo-solution. To cite this article: A. Dahmani, F. Bouhmila, C. R. Acad. Sci. Paris, Ser. I 343 (2006).     

Un algorithme probabiliste de calcul d'approximations polynômiales sur un hypercube

We describe a Monte Carlo method which enables an iterative computation of the L² approximation of a function on any orthonormal basis. We use it for the approximation of smooth functions on an hypercube with the help of multidimensional orthogonal polynomial basis containing only few terms. The algorithm is both a tool for approximation and numerical integration. To cite this article: S. Maire, C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

On the uniqueness of overcomplete dictionaries, and a practical way to retrieve them

A full-rank under-determined linear system of equations Ax = b has in general infinitely many possible solutions. In recent years there is a growing interest in the sparsest solution of this equation—the one with the fewest non-zero entries, measured by ∥x∥₀. Such solutions find applications in signal and image processing, where the topic is typically referred to as “sparse representation”. Considering the columns of A as atoms of a dictionary, it is assumed that a given signal b is a linear composition of few such atoms. Recent work established that if the desired solution x is sparse enough, uniqueness of such a result is guaranteed. Also, pursuit algorithms, approximation solvers for the above problem, are guaranteed to succeed in finding this solution.Armed with these recent results, the problem can be reversed, and formed as an implied matrix factorization problem: Given a set of vectors {b_i}, known to emerge from such sparse constructions, Ax_i = b_i, with sufficiently sparse representations x_i, we seek the matrix A. In this paper we present both theoretical and algorithmic studies of this problem. We establish the uniqueness of the dictionary A, depending on the quantity and nature of the set {b_i}, and the sparsity of {x_i}. We also describe a recently developed algorithm, the K-SVD, that practically find the matrix A, in a manner similar to the K-Means algorithm. Finally, we demonstrate this algorithm on several stylized applications in image processing.     

Minimal string difference encodings

Given two strings s and t, a difference encoding is a third string that contains sufficient information to derivet t from s. An algorithm is presented which derives a difference encoding that can be represented in the fewest number of bits relative to the string edit operators insert, delete, replace, and skip. This algorithm has practical significance for distributed text processing applications.     

Résolution de problèmes hyperélastiques de recalage d'imagesResolution of some hyperelastic image-matching problems

We focus on some image-matching problems that are based on hyperelastic strain energies. We design an algorithm that solves numerically the Euler–Lagrange equations associated to the problem. This algorithm is formulated in terms of an ODE (Ordinary Differential Equation). We give a theorem which states that the ODE has a unique solution and converges to a solution of the Euler–Lagrange equations. To cite this article: F.J.P. Richard, C. R. Acad. Sci. Paris, Ser. I 335 (2002) 295–299.     

Solution of Ulam's problem on searching with a lie

S. M. Ulam, (“Adventures of a Mathematician,” Scribner's, 1976.) stated the following problem: what is the minimal number of yes-no queries needed to find an integer between one and one million, if one lie is allowed among the answers. In Rivest et al. (J. Comput. System Sci 20, 396–404 (1980) and Spencer, (Math. Mag. 57, 105–108 (1984) partial solutions were given by establishing bounds for the minimal number of queries necessary to find a number in the set {1,…, n}. Applied to the original question both solutions yield two possibilities: 25 or 26. We give an exact solution of Ulam's problem in the general case. For n = 10⁶ the answer turns out to be 25. We also give an algorithm to perform the search using the minimal number of queries.     

An interior point potential reduction algorithm for the linear complementarity problem

The linear complementarity problem (LCP) can be viewed as the problem of minimizingx ^T y subject toy=Mx+q andx, y?0. We are interested in finding a point withx ^T y <ε for a givenε > 0. The algorithm proceeds by iteratively reducing the potential function $$f(x,y) = \rho \ln x^T y - \Sigma \ln x_j y_j ,$$ where, for example,ρ=2n. The direction of movement in the original space can be viewed as follows. First, apply alinear scaling transformation to make the coordinates of the current point all equal to 1. Take a gradient step in the transformed space using the gradient of the transformed potential function, where the step size is either predetermined by the algorithm or decided by line search to minimize the value of the potential. Finally, map the point back to the original space. A bound on the worst-case performance of the algorithm depends on the parameterλ ^*=λ^*(M, ε), which is defined as the minimum of the smallest eigenvalue of a matrix of the form $$(I + Y^{ - 1} MX)(I + M^T Y^{ - 2} MX)^{ - 1} (I + XM^T Y^{ - 1} )$$ whereX andY vary over the nonnegative diagonal matrices such thate ^T XYe ?ε andX _jj Y _jj?n ². IfM is a P-matrix,λ ^* is positive and the algorithm solves the problem in polynomial time in terms of the input size, |log ε|, and 1/λ ^*. It is also shown that whenM is positive semi-definite, the choice ofρ = 2n+ \(\sqrt {2n} \) yields a polynomial-time algorithm. This covers the convex quadratic minimization problem.     

Approximation numérique d'un problème de membrane non linéaire

We study numerically the deformations of a nonlinearly elastic membrane. We consider the nonlinear membrane model obtained by Le Dret and Raoult using Γ-convergence. In this model, membrane deformations minimize a highly nonquadratic energy. We consider a conforming finite element approximation of the problem and use a nonlinear conjugate gradient algorithm to minimize the discrete energy. To cite this article: N. Kerdid et al., C. R. Acad. Sci. Paris, Ser. I 340 (2005).     

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.     

Un algorithme de Schur pour les fonctions de transfert des systèmes surdéterminés invariants dans une direction

We define an analogue of the Schur algorithm for transfer functions of lossless 2D systems which are invariant with respect to one of the variables. To cite this article: D. Alpay et al., C. R. Acad. Sci. Paris, Ser. I 347 (2009).     

A policy iteration algorithm for zero-sum stochastic games with mean payoff

We give a policy iteration algorithm to solve zero-sum stochastic games with finite state and action spaces and perfect information, when the value is defined in terms of the mean payoff per turn. This algorithm does not require any irreducibility assumption on the Markov chains determined by the strategies of the players. It is based on a discrete nonlinear analogue of the notion of reduction of a super-harmonic function. To cite this article: J. Cochet-Terrasson, S. Gaubert, C. R. Acad. Sci. Paris, Ser. I 343 (2006).     

Complex Pisot numbers of small modulus

We use an algorithm of Chamfy to determine all complex Pisot numbers of modulus less than 1.17. To cite this article: D. Garth, C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

An analysis of (h,k, 1)-Shellsort

One classical sorting algorithm, whose performance in many cases remains unanalyzed, is Shellsort. Let h be a t-component vector of positive integers. An h-Shellsort will sort any given n elements in t passes, by means of comparisons and exchanges of elements. Let S>_j(h; n) denote the average number of element exchanges in the jth pass, assuming that all the n! initial orderings are equally likely. In this paper we derive asymptotic formulas of S_j(h; n) for any fixed h = (h, k, l), making use of a new combinatorial interpretation of S₃. For the special case h = (3, 2, 1), the analysis is further sharpened to yield exact expressions.     

Error-free computer solution of certain systems of linear equations

In this article we propose a procedure which generates the exact solution for the system Ax = b, where A is an integral nonsingular matrix and b is an integral vector, by improving the initial floating-point approximation to the solution. This procedure, based on an easily programmed method proposed by Aberth [1], first computes the approximate floating-point solution x^* by using an available linear equation solving algorithm. Then it extracts the exact solution x from x^* if the error in the approximation x^* is sufficiently small. An a posteriori upper bound for the error of x^* is derived when Gaussian Elimination with partial pivoting is used. Also, a computable upper bound for |det(A)|, which is an alternative to using Hadamard's inequality, is obtained as a byproduct of the Gaussian Elimination process.