3
$\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.

  • 3
    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.2012-06-14
  • 1
    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.2012-06-14
  • 0
    @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}}$.2014-01-07

2 Answers 2