TY - GEN
T1 - An even faster solver for general systems of equations
AU - Fecht, Christian
AU - Seidl, Helmut
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1996.
PY - 1996
Y1 - 1996
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84957649278&partnerID=8YFLogxK
U2 - 10.1007/3-540-61739-6_42
DO - 10.1007/3-540-61739-6_42
M3 - Conference contribution
AN - SCOPUS:84957649278
SN - 3540617396
SN - 9783540617396
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 189
EP - 204
BT - Static Analysis - 3rd International Symposium, SAS 1996, Proceedings
A2 - Cousot, Radhia
A2 - Schmidt, David A.
PB - Springer Verlag
T2 - 3rd International Static Analysis Symposium, SAS 1996
Y2 - 24 September 1996 through 26 September 1996
ER -