Christian Fecht and Helmut Seidl. An Even Faster Solver for General Systems of Equations. In Radhia Cousot and David A. Schmidt, editors, Static Analysis, volume 1145 of Lecture Notes in Computer Science, pages 189-204, Aachen, Germany, September 1996. Springer.
We present a new algorithm which computes a partial approximate solution for a system of equations. It is local in that it considers as few variables as necessary in order to compute the values of those variables we are interested in, it is generic in that it makes no assumptions on the application domain, and it is general in that the algorithm does not depend on any specific properties of right-hand sides of equations. For instance, monotonicity is not required. However, in case the right-hand sides satisfy some weak monotonicity property, our algorithm returns the (uniquely defined) least solution. The algorithm meets the best known theoretical worstcase complexity of similar algorithms. For the application of analyzing logic languages, it also gives the best practical results on most of our real world benchmark programs.
Download: PDF Reference: Bibtex The original publication is available at www.springerlink.com