Imagine a friend has a polynomial p(x) with rational coefficients,
but they won't tell you its expression, or even its degree. If you
give her any specific value for x, she will however give you
the corresponding value p(x). Can you reconstruct the
polynomial? In this project we will look at the most efficient
ways to do this.
In practice this is extremely useful in many situations (not only when you have a somewhat
bizarre friend). One common example performing Gaussian elimination
on a huge matrix with polynomials. This can get horrendously
complicated, with intermediate expressions getting bigger and
bigger.
The idea then is instead
to perform the Gaussian elimination for several numerical
values of x (which is much quicker) and then reconstruct the
full answer from these values.
However even performing Gaussian elimination for numerical values (inputting small integers
for example) the inetermediate expressions can become
very very large integers, slowing down the computation and increasing the
memory needed. In this case it is useful to implement modulo
arithmetic and use the rational reconstruction algorithm, a
method for finding a rational number from its value modulo a
sufficiently large integer m. This, together with the Chinese
remainder theorem, allows one to reconstruct fucntions purely
from values modulo a few different primes.
A main goal for this project could be to construct and test an algorithm
for achieving this reconstruction and then generalise to functions of more than
one variable and to rational functions rather than just polynomials.
This project has an obviously computational direction, although there is
plenty of new mathematics (as well as novel applications of
known mathematics) for you to get stuck into as well!
Lost of wikepdia articles inroduce the ingredients very nicely
To reconstruct the rational function from values it is nicest to use:
The Newton
polynomial representation of a polynomial
Then to use values modulo p and avoid very large values one needs
The
Rational Reconstruction Algorithm which uses the:
The
Extended Euclidean Algorithm
in turn using
Bezout's
identity
together with
The
Chinese Remainder Theorem
Putting this (and more) altogether has been described in two recent (physics
oriented) papers
https://arxiv.org/pdf/1406.4513.pdf
and https://arxiv.org/pdf/1608.01902.pdf
email: Paul
Heslop