Abstract:
A much-celebrated method for fast algorithms is to do computation on shadows of mathematical objects, instead of on the objects themselves. This only works because we can reconstruct objects from several shadows. Usually, these methods are used for computation with whole numbers and fractions of whole numbers. For my research project, I showed that these methods generalise to a certain type of more complicated number system.
Blog post:
There are a several graphics engines with demos that show off their lighting by pointing a light source at an object and projecting the shadow behind it. You can move the object around and rotate it to see how the shadow changes. For a mathematician, this is way to turn something complicated, like a 3D object, into something much simpler, a 2D shape. However, we lose some information about the object when we take its shadow. It’s not hard to imagine two distinct 3D objects that cast the same shadow from a certain angle.
In computer algebra, the field of mathematics where we study exact and symbolic computation, we analogously find different shadows of mathematical objects. We call these shadows modular images. If our object is one containing integers (whole numbers), we can consider the modular image where we replace all the integers with their remainders when divided by some fixed integer, called the modulus. For example, the vector [502, 492, -252] is sent to [-4, -3, 1] when we take the modulus to be 11.
Since objects are usually much larger than their modular images, it is often much easier for computers to work with modular images. Therefore, we consider the inverse problem to projecting shadows: given several shadows of an object, can we reconstruct the object that must have cast them?
It turns out that when shadows are modular images of objects containing integers or fractions of integers, the inverse problem can be solved! Instead of doing expensive computations on a complex object directly, we can very quickly and efficiently perform computations on several modular images of the object, and then reconstruct the result we were looking for from the images. This is a very celebrated and widely used concept in computer algebra.
For my research project, I was interested in trying to extend modular algorithms to work over more complex number systems than just the integers. I focused on trying to extend modular algorithms to perform fast computation in quadratic number fields; that is, number systems containing both the fractions of integers and the square root of an integer. For integer modular algorithms, we almost always pick a prime modulus. One of the biggest questions I had to consider was how to generalise the idea of a prime modulus, and how to produce an algorithm to compute these generalised primes.
Fortunately, everything worked out and I have an example of a generalised modular algorithm running on a computer, along with proofs that all the algorithms work! The algorithm I chose to write solves systems of linear equations in quadratic number fields, and it does this significantly faster than non-modular methods!
Mitchell Holt
The University of Queensland
