Abst rac t

Given a set of m observations on n variables, an 0(mn2) algorithm is proposed to find a ba-sis of all affine relations between these variables satisfied by the observations. On a 25 variables example, this new algorithm is 130 000 times faster than the "all subsets " option for linear regression of the SAS package which is a non polynomial alternative. Extension to the cases where squares, ratios, products of pairs of vari-ables or logarithms of such terms appear in the relations is straightforward and remains poly-nomial. The method is first tested with data for several classical discoveries studied previously by the Bacon programs. Then it is added to the AutoGraphiX system for computer-aided grap