# How to do (m)Gram-Schmidt orthogonalization with integers ? (real life problem) (“mathematicalized reformulation”)

New edition of the question, "mathematicalized" (thanks to Gerhard).

Consider and integer valued n*n matrix M, with integers elements in the range -N < m < N. I want to find integer-valued approximate orthogonalization of this matrix X. Means that values of X are integers in the same range and matrix is "close" to the honest Gram-Schmidt orthogonalization of initial matrix X_honest.

Is there some bound norm ( X- X_honest) > f( condition(M) ) ? E.g. it is difficult to solve the problem if original matrix is ill-conditioned.

Is there way to find such matrix in reasonable complexity O(n^3) ? (and not using sophistaced arithmetical representation of numbers e.g. emulation of floating point or rational or Chinese remainder theorem is not allowed).

=========== Try to do orthogonalization of these column vectors. Problem is that the 3-th and 4-th are almost the same. Is there some nice solution ? Or some no-go result can be proved that with integers I cannot do this ? Or I can do it but not within reasonable complexity O(n^3) ?

[ 32768.000000 , 0.000000 , -1424.000000 , -1422.000000 ; ...

24219.000000 , 10476.000000 , 3107.000000 , 3109.000000 ; ...

-18861.000000 , -22098.000000 , 32768.000000 , 32768.000000 ; ...

-20462.000000 , 32768.000000 , 3939.000000 , 3940.000000 ];

More details. The processing units used in fast or low-energy computing devices like mobile phones, GPS, signal processors do not support floating point arithmetics. I.e. they can work we integers e.g. -2^15 <= m <2^15-1 And when you do multiplication of such two must truncate result back to this region before you can do any other operation.

The task is do Gram-Schmidt orthogonalization of a matrix on such device. When I do it I see that resulting vectors are far from orthogonal Matrix of normalized scalar products is the following:

1.0000    0.0000    0.0000    0.1764

0.0000    1.0000    0.0000    0.5667

0.0000    0.0000    1.0000    0.4438

0.1764    0.5667    0.4438    1.0000


Is there some nice way to cure the problem or no ? I would prefer that complexity (i.e. number of operations) is not much bigger that in standard algorithm. i.e. O(n^3).

-
You can represent rationals in the algorithm exactly as fractions (pairs of integers). Making it fit in two-byte integers may be a bigger problem, especially since your input numbers do not seem to fit there in the first place (32768). – Emil Jeřábek Oct 27 '11 at 17:57
Vague comment: would it help to use modular arithmetic for various moduli and use the Chinese Remainder Theorem to patch things back together? – Matt Young Oct 27 '11 at 18:16
Do as you feel best, Igor. I have a feeling there are some meaty numerical analysis issues, perhaps a result that says there is a condition number above which a nice answer is guaranteed, and that the condition number may be computed quickly. I hope others take more time in casting closing votes. Also, if the user is dealing only with 4x4 integer arrays, there may be a nifty answer. Gerhard "Ask Me About System Design" Paseman, 2011.10.27 – Gerhard Paseman Oct 27 '11 at 19:50
How are you computing the orthogonal vectors? Pure Gram-Schmidt is the obvious incorrect choice; have you tried using Householder reflections? Those are going to be stabler for a given precision than standard Gram-Schmidt when columns are near-orthogonal. Trefethen and Bau's book would be a good place to look, and Demmel's book would have a comprehensive collection of algorithms for specific situations. – Nilima Nigam Oct 28 '11 at 3:54
The matrix appears nearly rank deficient, so I'd suggest using methods for rank-deficient QR decompositions with column pivoting. The key would be Householder/Givens rotations rather than projections. As Igor suggests, Golub and van Loan's book has lots on the numerical analysis of this. Demmel's book will point you to algorithms for your particular situation. – Nilima Nigam Oct 29 '11 at 14:36