Math Table/Open Neighborhood Seminar: Why are p-adic numbers useful for fast linear algebra algorithms?
Silvia Casacuberta Puig - Harvard Undergraduate
p-Adic numbers have always been primarily associated with pure Mathematics, and have become especially relevant in algebra and modern number theory. But why did Computer Scientists become interested in them? In this talk we will introduce p-adic numbers and survey their main properties. We will then introduce Dixon’s algorithm, which is the first algorithm that used p-adic numbers to compute the exact rational solution to an integer linear system of equations. We will also explore the latest runtime improvements in p-adic linear algebra algorithms, and discuss whether we can solve linear equation systems faster than matrix multiplication.