Computing Longest Previous Factor in linear time and applications

We give two optimal linear-time algorithms for computing the Longest Previous Factor (LPF) array corresponding to a string w. For any position i in w, LPF[i] gives the length of the longest factor of w starting at position i that occurs previously in w. Several properties and applications of LPF are investigated. They include computing the Lempel-Ziv factorization of a string and detecting all repetitions (runs) in a string in linear time independently of the integer alphabet size.     

Identification of certain noisy MA models: new results

In this paper, we address the identification problem of p-inputs q-outputs MA models, corrupted by a white noise with unknown covariance matrix, in the case where p<q. Under certain additional conditions, we show that the generating function of the MA model is identifiable (up to a p×p constant orthogonal matrix) from the autocovariance function of the observation. Our results extend those already obtained in Desbouvries et al. [5] and Desbouvries and Loubaton [6].     

Linear Operator Inequalities for Strongly Stable Weakly Regular Linear Systems

We consider the question of the existence of solutions to certain linear operator inequalities (Lur'e equations) for strongly stable, weakly regular linear systems with generating operators A, B, C, 0. These operator inequalities are related to the spectral factorization of an associated Popov function and to singular optimal control problems with a nonnegative definite quadratic cost functional. We split our problem into two subproblems: the existence of spectral factors of the nonnegative Popov function and the existence of a certain extended output map. Sufficient conditions for the solvability of the first problem are known and for the case that A has compact resolvent and its eigenvectors form a Riesz basis for the state space, we give an explicit solution to the second problem in terms of A, B, C and the spectral factor. The applicability of these results is demonstrated by various heat equation examples satisfying a positive-real condition. If (A, B) is approximately controllable, we obtain an alternative criterion for the existence of an extended output operator which is applicable to retarded systems. The above results have been used to design adaptive observers for positive-real infinite-dimensional systems. Date received: July 25, 1997. Date revised: February 10, 2001.     

Necessary and sufficient conditions on Q ( = C( I + PC)) for stabilization of the linear feedback system S(P, C)

We find the following necessary and sufficient conditions for Q (:=C(I+PC)⁻¹) to -stabilize the standard linear time-invariant unity feedback system S(P, C) where P has the l.c.f. (D_pl, N_pl) and the r.c.f. (N_pr, D_pr); and is a principal ideal domain. (i) Q must have elements in (ii) (resp. (iii)) Q must factorize in with D_pr, (resp. D_pl) as a left (resp. right) factor and (iv) (I – QP) must factor in with D_pr, as a left factor.     

Collaborative filtering with interlaced generalized linear models

Collaborative filtering (CF) is a data analysis task appearing in many challenging applications, in particular data mining in Internet and e-commerce. CF can often be formulated as identifying patterns in a large and mostly empty rating matrix. In this paper, we focus on predicting unobserved ratings. This task is often a part of a recommendation procedure. We propose a new CF approach called interlaced generalized linear models (GLM); it is based on a factorization of the rating matrix and uses probabilistic modeling to represent uncertainty in the ratings. The advantage of this approach is that different configurations, encoding different intuitions about the rating process can easily be tested while keeping the same learning procedure. The GLM formulation is the keystone to derive an efficient learning procedure, applicable to large datasets. We illustrate the technique on three public domain datasets.     

Expression for massively parallel algorithms — description and illustrative example

In this paper, we present a way of expressing massively parallel algorithms associated with a programming environment for networks of processors with local memory; the aim is to provide a programming method that is independent of the network topology, and that leads to an efficient implementation for communications.

Then, we illustrate these concepts using as an example a scientific algorithm: Choleski's method for a parallel factorization of sparse matrices into blocks.

This work gives rise to software for a T.Node multiprocessor computer.     

Fast separable factorization and applications

In this paper we show that the separable decomposition of a univariate polynomial can be computed in softly optimal time, in terms of the number of arithmetic operations in the coefficient field. We also adapt the classical multi-modular strategy that speeds up the computations for many coefficient fields, and we analyze consequences of the new results to the squarefree and the irreducible factorizations. This work was partly supported by the French Research Agency via the Gecko project (gecko.inria.fr).     

Solution of sparse positive definite systems on a shared-memory multiprocessor

Algorithms and software for solving sparse symmetric positive definite systems on serial computers have reached a high state of development. In this paper, we present algorithms for performing sparse Cholesky factorization and sparse triangular solutions on a shared-memory multiprocessor computer, along with some numerical experiments demonstrating their performance on a Sequent Balance 8000 system.Research was supported by the Applied Mathematical Sciences Research Program of the Office of Energy Research, U.S. Department of Energy under contract DE-AC05-84OR21400 with Martin Marieta Energy Systems, Inc., by the U.S. Air Force Office of Scientific Research under contract AFOSR-ISSA-85-00083 and by the Canadian Natural Sciences and Engineering Research Council under grants A8111 and A5509.     

Minimal representations of continuous-time processes having spectral density with zeros in the extended imaginary axis

Given a process y with stationary increments and rational incremental spectral density Φ(s), we parametrize minimal state-space representations of dy. We consider the case when Φ(s) may have zeros on the imaginary axis including infinity and we analyze the zero structure of each state-space representation.