Thursday, 25 October 2007

linear algebra - Extracting integer multiplicative factors from the sum of certain sets of (finite-precision) real numbers?

Update based on Michael's answer (thanks again!) - Can the LLL or PSLQ algorithms provide a (knowably - i.e. not just incidental) unique solution for the set of integer multiplicative factors? Are there other algorithms (perhaps with worse run-time complexities) that can?



Imagine that one has a set of 'n' finite-precision real numbers - (r_1, r_2, ..., r_n), each with an associated positive integer multiplicative factor, (i_1, i_2, ..., i_n). Here, one only has access to the values in the set of real numbers, as well as the sum of the real numbers multiplied by their corresponding multiplicative factors, 'S', i.e. - Sum(i_1*n_1, i_2*n_2, ..., i_n*r_n).



What's the most efficient way to test that the sum of a particular set of real numbers will (or, obviously, will not) always allow us to extract a unique solution for the set of integer multiplicative factors? Or to find/do this with fewest restrictions on the values of the integer multiplicative factors?



In the case that this has a very simple answer, apologies.



(Edit - Changed "each with an associated "set of" positive integer multiplicative factors" --> "each with an associated positive integer multiplicative factor". One finite-precision real number 'r_k' has one integer multiplicative factor 'i_k'.)

No comments:

Post a Comment