A faster solver for general systems of equations

We present a new algorithm which computes a partial approximate solution fo r a system of equations. It is local in that it considers just as many vari ables 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 applic ation domain, and it is general in that the algorithm does not depend on an y specific properties of right-hand sides of equations. For instance, monot onicity is not required. However, in case the right-hand sides satisfy some weak monotonicity property, our algorithm returns the (uniquely defined) l east solution. The algorithm meets the best theoretical worstcase complexit y known for similar algorithms. For the application of analyzing logic lang uages, it also gives the best practical results on most of our real-world b enchmark programs. (C) 1999 Elsevier Science B.V. All rights resented.