MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

5 deleted 52 characters in body

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).

4 "mathematicalized" the problem

# How to do (m)Gram-Schmidt orthogonalization with integers ? (real life problem) ("mathematicalizedreformulation")

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(N) ) ? E.g. moral is that it is difficult to solve the problems 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).

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 orhtogonalization http://en.wikipedia.org/wiki/GramSchmidt_process 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 algorihmalgorithm. i.e. O(n^3).

2 edited title
1