A working back-substitution routine is:
backsub=:3 :0
n=.# (-. 0...@{.) y
firstind=. i.&1@:~:&0
for_i. i.&.<: n do.
'ind pivot'=.(firstind ([ , {) ]) i{r
mult=.n {. - pivot <....@%~ ind ([ {"1 {.) r
r=. (mult */ i{r) + r
end.
)
backsub@:rowreduceint puts an integer matrix A into an upper triangular form
so that:
Zero rows are at the bottom.
The first element of each row is positive, and these first values do not
decrease for later rows.
If a row has first element e, all other numbers in that column are zero if
they are below e and between zero and (e-1) if they are above it.
This is about the closest you get to reduced row echelon for integer
matrices.
I can't really post representative timings because for random matrices using
this process the entries become giant (ie. 10^173 for 100 1...@$10).
Marshall
-----Original Message-----
From: Marshall Lochbaum [mailto:[email protected]]
Sent: Sunday, December 12, 2010 10:17 AM
To: 'Programming forum'
Subject: RE: [Jprogramming] Solving diophantine equations
A while ago I made a integer row-reduction routine that does the equivalent
of forward elimination for integer matrices:
rowreduceint=:3 :0
if. 0=*/$y do. y return. end.
y=.(* <:@+:@(>&0)@{."1) y
n=.+/*{."1 y
if. n=0 do. 0,.rowreduceint }."1 y return. end.
while. n>1 do.
i=.(i.<./) (+ _*=&0) {."1 y
y=.y - (i{y)*/~ 0 i} (<....@% i&{) {."1 y
n=.+/*{."1 y
end.
y=. \:~ y
({.y) , 0,. rowreduceint 1 1}. y
)
You could run this on the extended matrix A|y as a start to solving the
integer equation Ax=y . Then you would have to find a good way to do
back-substitution, because it will not work perfectly with integer matrices.
Marshall
-----Original Message-----
From: [email protected]
[mailto:[email protected]] On Behalf Of Justin Paston-Cooper
Sent: Sunday, December 12, 2010 3:18 AM
To: Programming forum
Subject: [Jprogramming] Solving diophantine equations
Hello,
Could anyone please tell me what facilities there are for J for solving
diophantine equations? Specifically, I have square integer matrices A of
rank n, and I want to find integer vectors x of length n such that xA = y
(another integer vector) and x.x = z (an integer).
I'll also have cases where it is useful to find scalars z with xAx = z.
Have such packages been written for J? Should I be looking somewhere else?
I've been working with Mathematica, and it hasn't been particularly fast.
Thanks in advance,
Justin
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
