There is a generator to create perfect pythagorean triples…3:4:5, 5:12:13… http://www.mathreference.com/num-zext,pt.html
for x^2+y^2=z^2,
x=u^2-v^2
y=2uv
z=u^2+v^2
when u and v are coprime.

For that, you don’t want a 3rd power Diophantine equation; you want a 2nd power one with three terms. That is, you want integers a, b, and c such that a^2 + b^2 = d^2, b^2 + c^2 = e^2, a^2 + c^2 = f^2, and a^2 + b^2 + c^2 = g^2, where d, e, f, and g are all also integers. There’s no cubes here.

One way to “solve” the Integer Brick (for integral sides and an integral body diagonal, but not necessarily face diagonals) is to realize that the square of (a + b) is a^2 +2ab + b^2. So if two sides are a and b and you arrange that the square of the third side is 2ab = c^2, the body diagonal will be a + b.
The most obvious solution is a = 1, b = 2, c = 2, with diagonal 3 (and multiples of these), but this is not the only solution you can generate. You can also get a = 2 b = 9, c = 6 with diagonal 11, for instance. You can use this to generate an infinite number of solutions, not all of them multiples of lower-order solutions. The only trick is choosing the value of 2 ab = c^2, and the rest falls into place.

I halfway suspected that you were really trying to turn this into a linear algebra problem and that linear programming was a red herring. And as you’ve realized, linear algebra is used to solve (systems of) linear equations and is not really suited to this problem.

Not true – look at my post above. It is an infallible method of generating Pythagorean triples (quadruples?). And it doesn’t require that you test all possible triples.

I suspect that it won’t generate all possible integral pytrhagorean triples (quadruples?). But then again, the method you cite in your OP demonstrably doesn’t generate all Pythagorean triples of the form a^2 + b^2 = c^2.

Another option remains. You could prove that no solution exists. The advantage to this approach is that I strongly suspect that it is the only thing that has a non-zero probability of meeting success.

The OP’s method generates all Pythagorean triples in “lowest terms”; to generate all Pythagorean triples more generally, one just takes all the multiples of these.

AFAIK, that’s true. And it generates many of the multiples of the “lowest terms”, but not all of the multiples, as I’ve demonstrated myself. Although it generates all of the lowest Pythagorean triples i know of (at least in “lowest terms”), I must admit that I don’t know that it will generate all of the triples in “lowest terms”.

You don’t need a ton of memory, so long as you have some systematic way of going through the possible solutions. You don’t have to take up memory storing one that didn’t work; you just throw it out and move on to the next candidate. And each individual candidate takes up a small amount of memory.

Now, what you do need is a different way of managing your memory, since the standard integer data types aren’t large enough for numbers this big. But you can get packages to facilitate this; others have solved that problem before.