5
$\begingroup$

Notwithstanding that it isn't numerical analysis if it's over finite fields, but what topics that are traditionally considered part of numerical analysis still have some substance to them if the reals are replaced with finite fields or an algebraic closure thereof? Perhaps using Hamming distance as a metric for convergence purposes, with convergence of an iteration in a discrete setting just meaning that the Hamming distance between successive iterations becomes zero i.e. the algorithm has a fixed-point.

I ask about still having substance because I suspect that in the ff setting, na topics will mostly either not make sense, or be trivial.

$\endgroup$
3
  • 3
    $\begingroup$ You are correct in the belief that many matters of interest to numerical analysts do not make sense or are trivial since all computations are exact. Root finding does not need to be concerned with accuracy, there are no ill-conditioned matrices that are difficult to deal with, there are no round-off errors that need be worried about, and so on. On the other hand, Gauss-Jordan elimination works (as Nate Iverson points out) as does Lagrange interpolation and so on. Efficient computational algorithms that work in finite fields are of great interest to coding theorists and cryptographers. $\endgroup$
    – Dilip Sarwate
    Commented Jun 14, 2012 at 15:10
  • 1
    $\begingroup$ One example comes to mind. It doesn't exactly involve finite fields, but rather finite residue class rings. I once solved a set of couple thousand quadratic congruence equations using the plain old Newton-Rhapson. The metric was not the Hamming metric but rather the product of all the $p$-adic metrics. Meaning: the distance between two integers $x$ and $y$ modulo $N$ (= relatively large number) was $$ d_N(x,y)=\begin{cases}0,&\ \text{if}\ x=y\\ \frac1{\gcd(N,x-y)},& \ \text{otherwise.}\end{cases} $$ It converged like charm, too. $\endgroup$
    – Jyrki Lahtonen
    Commented Jun 14, 2012 at 17:54
  • $\begingroup$ @DilipSarwate You are right that finite fields allow exact solustions. But it is not trivial to apply these solutions to real world numerical questions. E.g. software ond microcontrollers is often limited to integer operations, while the data is usually slightly scattered. So a good approximation theory in vector spaces over finite field makes sense, because of the ability to solve equations exactly. In that cases it might be useful to consinder something like Lee metrics in vector spaces over $\mathbb{Z_{2^n}}$. $\endgroup$
    – Keinstein
    Commented Jan 7, 2014 at 7:22

2 Answers 2

Reset to default
3
$\begingroup$

The people who factor large numbers using sieve algorithms (the quadratic sieve, the special and general number field sieves) wind up with enormous (millions by millions) systems of linear equations over the field of two elements, and they need to put a lot of thought into the most efficient ways to solve these systems if they want their algorithms to terminate before the sun does.

$\endgroup$
1
$\begingroup$

There is substantial interest in vector spaces over finite fields. Much of the research falls into the area of Computational group theory or computations in Modular Representation theory. In particular Gauss-Jordan Elimination works and if I recall correctly has the same computational complexity as over characteristic 0.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .