## File: kach.mc

package info (click to toggle)
maxima 5.6-17
 `123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162` ``````/* Hacijan Linear Programming Algorithm */ /* Implementation by Jim Purtilo ( JIMP@MIT-MC ) Kent State University November 1979 First added to share directory January 5, 1980 */ /* This version has more hooks for adding users definable criterion for stopping and restarting in mid alg; trying to solve the difficulty in loosing positive definitness in time. */ /* */ /* Primitives defined are: HACH( a , b , n , m , l ) where a is the matrix and b is the column vector such that a.x */ /* Note that there is a global variable show%all[false] which when true will print the vector x at each iteration. */ declare(z,special)\$ define_variable(show%all,false,boolean)\$ define_variable(last%row,0,any)\$ hach(a,b,n,m,l):= block([x,i,k,h,q,last%row], last%row:0, h:bfloat(2^(2*l)*ident(n)), x:genmatrix(z,n,1), /* Note this is a "do forever...", not automatically checking the counter k against in the stopping criterion of the theory. The reason for this is that oft' times we like to play with whacky L's, and don't want to mess with the resulting random stoppage. Next update will have a settable switch... and possibly also an improved polynomial stopping time... */ for k:0 next k+1 do if (i:check(a,b,x,m))=0 then return(["win",k,"iterations",x]) else ( if show%all then ( print(k,x),print(" ")), if not criterion(a,b,x,n,m,l,k) then iterate(x,a,h,q,i,n) else /* In here would be code for resetting, say, h, x , lastrow, etc. Then we start the iteration process again, hopefully accellerated. Note that for debugging purposes, code here could be a break... */ ( accelerate(a,b,x,n,m,l,k), iterate(x,a,h,q,i,n) ) ) )\$ accelerate(a,b,x,n,m,l,k):=false\$ criterion(a,b,x,n,m,l,k):=true\$ /* for now the above will keep things runningtill the users defined what he wants... */ check(a,b,x,m):= block([y,j,j1], j1:0, y:a.x, if numberp( last%row ) then if last%row#0 then if ">="(y[last%row,1],b[last%row,1]) then j1:last%row, if j1#0 then return( j1 ), for j:1 thru m do if ">="(y[j,1],b[j,1]) then j1:j, j1 /* Note that this strategy is that if last%row is ok, or is undefined due to a user CHECKing a system, the the first row violating a.x