Hi,
Today, I committed my Fourier elimination code. In the folder
/share/contrib/fourier_elim/,
you'll find the source code and a rtest file. All tests except the last
six
should pass. Let me know if that's not the case.
Fourier elimination triangularizes linear inequalities in much the same
way as
Gauss elimination triangularizes linear equations. An few examples might
be
all you need to understand Fourier elimination:
(%i14) fourier_elim([0 < x, x < 1, 0 < y, y < 1, 0 < z, z + y + x <
4],[z,y,x]);
(%o14) [0 < z,z < -y-x+4,0 < y,y < 1,0 < x,x < 1]
Mixed linear equations and inequalities are OK:
(%i15) fourier_elim([x + y = 1, x < 1],[x,y]);
(%o15) [x = 1-y,0 < y]
There is a preprocessor that tries to convert to a linear form: two
examples
(%i16) fourier_elim((x + 1) / (x - 1) < 10,[x]);
(%o16) [11/9 < x] or [x < 1]
(%i17) fourier_elim(abs(x) + abs(x/2) + abs(x / 3) # 1,[x]);
(%o17) [x = 0] or [0 < x,x < 6/11] or [-6/11 < x,x < 0] or [6/11 < x] or
[x < -6/11]
Fourier elimination is costly. Depending on what you need, the simplex
method
(Andrej Vodopivec, author) might be a (much) faster alternative.
Let me know if you find bugs. If this code is something that might be
useful,
maybe I'll even write some user documentation :) Till then, the rtest file
should give you an idea of what fourier_elim can do.
By the way: One thing I needed to change for 5.14.0 was
(memq ($compare a b) '(&< &<=)) --> (member ($compare a b) '("<" "<=")
:test 'equal)
I think that (memq ($compare a b) '("<" "<=")) doesn't do the job.
Barton