Eliminazione gaussiana Modulo P

Question

Sto cercando di riscrivere un codice in Java risolvendo un insieme di equazioni lineari facendo eliminazione gaussiana sui galleggianti, per lavorare sulle equazioni modulo un primo. Il problema è che non funziona, e non riesco a capire cosa c'è che non va. Sembra lavorare su piccoli gruppi di equazioni, ma non su grandi gruppi, il che rende difficile il debug.

Il mio algoritmo prendi la prima riga, normalizzarlo trovando l'inverso al primo elemento e moltiplica ogni elemento nella riga da questo inverso. Quindi sottrae questa riga dalle altre righe abbastanza volte a rendere il loro primo elemento zero. Sulla prossima iterazione va alla riga successiva e fare la stessa procedura, fino a quando l'elemento girevole di riga è in colonna I. Infine sottrae ogni riga dalle precedenti righe per fare solo un elemento non zero di ogni colonna (tranne l'ultimo). (A partire da ora uso doppi, che non è necessario, ma questo non dovrebbe essere un problema). Ecco il mio codice:

// Transforms A so that the leftmost square matrix has at most one 1 per row,
    // and no other nonzero elements.
    // O(n^3)
 public static void gauss(int[][] A, int num_columns) {
        int n = A.length;
        int m = A[0].length;

        for (int i = 0; i < num_columns; i++) {
            // Finding row with nonzero element at column i, swap this to row i
            for(int k = i; k < num_columns; k++){
                if(A[k][i] != 0){
                    int t[] = A[i];
                    A[i] = A[k];
                    A[k] = t;
                }
            }
            // Normalize the i-th row.
            int inverse = (int)inverse((long)A[i][i], prime);
            for (int k = i ; k < m; k++) A[i][k] = (A[i][k]*inverse) % prime;

            // Combine the i-th row with the following rows.
            for (int j = 0; j < n; j++) {
                if(j == i) continue;
                int c = A[j][i];
                A[j][i] = 0;
                for (int k = i + 1; k < m; k++){
                    A[j][k] = (A[j][k] - c * A[i][k] + c * prime) % prime;
                }
            }
        }
    }

    public static void gauss(int[][] A) {
        gauss(A, Math.min(A.length, A[0].length));
    }
    public static long gcd(long a, long b){
        if(a < b){
            long temp = a;
            a = b;
            b = temp;
        }
        if(b == 0) return a;
        return gcd(b, a % b);
     }
    public static Pair ext_euclid(long a, long b){
        if(a < b){
            Pair r = ext_euclid(b,a);
            return new Pair(r.second, r.first);
        }
        if(b == 0) return new Pair(1, 0);
        long q = a / b;
        long rem = a - b * q;
        Pair r = ext_euclid(b, rem);
        Pair ret = new Pair(r.second, r.first - q * r.second);
        return ret;
    }

    public static  long inverse(long num, long modulo){
        num = num%modulo;
        Pair p = ext_euclid(num, modulo);
        long ret = p.first;
        if(ret < 0) return (modulo + ret) % modulo;
        return ret % modulo;
    }

    static class Pair{
        public long first;
        public long second;
        public Pair(long frst, long scnd){
            first = frst;
            second = scnd;
        }
    }

.

funziona su piccoli esempi (mod 29):

matrix = {{1.0, 1.0, 1.0, 1.0}, {1.0, 2.0, 1.0, 2.0},{1.0, 0.0, 0.0‚ 3.0}};
answer= {{1.0, 0.0, 0.0, 0.0},{0.0, 1.0, 0.0, 1.0}, {0.0, 0.0, 1.0, 0.0}};

.

che è corretto (prima variabile= 0, secondo= 1,0, terzo= 0), come può essere controllato da wolframalpha per 0 * k ^ 0 + 1 * k ^ 1 + 0 * k ^ 2 per k= 1. .3.

Per questo esempio, avendo 10 variabili e le equazioni A * K ^ 0 + B * K ^ 1 + C * K ^ 2 ... (Mod 29) per K= 1..11, ho questa matrice :

1 1 1 1 1 1 1 1 1 1 1 8 
1 2 4 8 16 3 6 12 24 19 9 5 
1 3 9 27 23 11 4 12 7 21 5 12 
1 4 16 6 24 9 7 28 25 13 23 12 
1 5 25 9 16 22 23 28 24 4 20 15 
1 6 7 13 20 4 24 28 23 22 16 0 
1 7 20 24 23 16 25 1 7 20 24 5 
1 8 6 19 7 27 13 17 20 15 4 1 
1 9 23 4 7 5 16 28 20 6 7 18 
1 10 13 14 24 8 22 17 25 18 7 20 
1 11 5 26 25 14 9 12 16 7 7 8  

.

Usando il mio algoritmo ottengo la risposta:

1 0 0 0 0 0 0 0 0 0 0 18 
0 1 0 0 0 0 0 0 0 0 0 8 
0 0 1 0 0 0 0 0 0 0 0 15 
0 0 0 1 0 0 0 0 0 0 0 11 
0 0 0 0 1 0 0 0 0 0 0 28 
0 0 0 0 0 1 0 0 0 0 0 27 
0 0 0 0 0 0 1 0 0 0 0 7 
0 0 0 0 0 0 0 1 0 0 0 21 
0 0 0 0 0 0 0 0 1 0 0 9 
0 0 0 0 0 0 0 0 0 1 0 24 
0 0 0 0 0 0 0 0 0 0 1 14  

.

Ma questo è sbagliato! (può essere controllato con wolframalpha). La risposta giusta dovrebbe essere (A B C ...)= (8 13 9 13 4 27 18 10 12 24 15).

Qualcuno può individuare il mio errore? O ho frainteso come fare gauss mod p?

Answer 1

Non sembra trovare una riga con un diverso da zero nella posizione Io durante il tuo primo stadio.Dato che, e il fatto che non so come funziona la funzione inverse, è possibile o potrebbe non essere in esecuzione in un problema lì.

Non capisco perché stai cercando "pivot" nella seconda fase.Sai dove sono dal primo stadio.In realtà, non vedo perché hai affatto un secondo stadio.Invece tutto l'eliminazione nella prima fase.Questo chiaristerà notevolmente il tuo codice.

Non capisco perché stai usando doubles nella tua matrice.Inoltre non capisco perché stai usando Math.abs dappertutto;I confronti dell'uguaglianza sono abbondanti qui.

Infine, stai risolvendo un sistema Vandermonde.Se questa è la tua applicazione, non solo un caso di test, dovresti probabilmente utilizzare invece l'interpolazione di LaGrange.