가우스 제거 모듈로 p

Question

저는 소수 모듈로 방정식을 작업하기 위해 부동소수점에서 가우스 제거를 수행하는 선형 방정식 세트를 해결하는 코드를 Java로 다시 작성하려고 합니다.문제는 작동하지 않고 무엇이 잘못되었는지 알 수 없다는 것입니다.작은 방정식 세트에서는 작동하는 것처럼 보이지만 큰 세트에서는 작동하지 않아 디버깅이 어렵습니다.

내 알고리즘은 첫 번째 행을 취하고, 첫 번째 요소에 대한 역수를 찾아 이를 정규화하고, 행의 모든 ​​요소에 이 역수를 곱합니다.그런 다음 첫 번째 요소를 0으로 만들기에 충분한 시간 동안 다른 행에서 이 행을 뺍니다.다음 반복에서는 다음 행으로 이동하여 i행의 피벗 요소가 i열에 있을 때까지 동일한 절차를 수행합니다.마지막으로 이전 행에서 모든 행을 빼서 모든 열(마지막 열 제외)에서 0이 아닌 요소를 하나만 만듭니다.(지금은 필요하지 않은 복식을 사용하지만 이는 문제가 되지 않습니다.)내 코드는 다음과 같습니다.

// 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;
        }
    }

이는 작은 예제(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}};

올바른 것입니다(첫 번째 변수 = 0, 두 번째 = 1.0, 세 번째 = 0). WolframAlpha에서 k = 1..3에 대해 0*k^0 + 1*k^1 + 0*k^2에 대해 확인할 수 있습니다.

이 예에서는 10개의 변수가 있고 방정식 a*k^0 + b*k^1 + c*k^2...(mod 29) k = 1..11에 대해 다음 행렬이 있습니다.

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  

내 알고리즘을 사용하여 답을 얻습니다.

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  

하지만 이건 틀렸어!(WolframAlpha로 확인 가능)정답은 (a b c ...) = (8 13 9 13 4 27 18 10 12 24 15)입니다.

누구든지 내 실수를 알아챌 수 있나요?아니면 내가 Gauss mod p를 수행하는 방법을 오해한 걸까요?

Answer 1

첫 번째 단계에서 i번째 위치에 0이 아닌 행을 찾지 못하는 것 같습니다.그걸 감안할 때, 그리고 내가 당신이 어떻게 지내는지 모른다는 사실을 고려하면 inverse 기능이 작동하면 문제가 발생할 수도 있고 발생하지 않을 수도 있습니다.

왜 두 번째 단계에서 "피벗"을 찾고 있는지 이해가 되지 않습니다.첫 번째 단계부터 그들이 어디에 있는지 알 수 있습니다.사실 왜 두 번째 단계가 있는지 전혀 모르겠습니다.대신 첫 번째 단계에서 모든 제거를 수행하십시오.이렇게 하면 코드가 크게 명확해집니다.

왜 사용하는지 이해가 안 돼요 double당신의 매트릭스에 있습니다.나는 또한 당신이 왜 사용하는지 이해하지 못합니다. Math.abs 모든 곳에;여기서는 평등 비교가 매우 적절합니다.

마지막으로 Vandermonde 시스템을 해결하고 있습니다.그것이 단지 테스트 사례가 아닌 귀하의 애플리케이션이라면 대신 라그랑주 보간법을 사용해야 할 것입니다.