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).
Best Answer
Well, if your microprocessors can handle fixed point arithmetic then here is a matlab commercial that should do it: http://www.mathworks.com/products/fixed/demos.html?file=/products/demos/shipping/fixedpoint/cordicqr_demo.html
Gram-Schmidt is not numerically stable even when you can use floating point so my guess is that you will have many problems if you stay that course.