A Note on Karr’s Algorithm Markus Müller-Olm1? and Helmut Seidl2

Abstract. We give a simple formulation of Karr’s algorithm for computing all affine relationships in affine programs. This simplified algorithm runs in time O(nk 3) where n is the program size and k is the number of program variables assuming unit cost for arithmetic operations. This improves upon the original formulation by a factor of k. Moreover, our re-formulation avoids exponential growth of the lengths of intermediately occurring numbers (in binary representa-tion) and uses less complicated elementary operations. We also describe a gener-alization that determines all polynomial relations up to degree d in time O(nk3d).