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 between condition number which says norm ( X- X_honest) > f( condition(Ncondition(M) ) ? E.g. moral is that it is difficult to solve the problems 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).
