java - 计算和编码线性代数(例如 Ax=B)的最短方法是什么

Question

我想知道计算 Ax=B 等线性代数的最短代码(ACM 等竞赛所需)是什么。这是我用高斯规则计算 Ax=B 的 java 代码:

public static void linearAlgebra(double[][] a , double[] b , double[] x , int n)
{
    for(int j = 0 ; j<n ; j++)
    {
        for(int i = 0 ; i<n ; i++)
        {
            if(j<i)//lower triangle of A matrix
            {
                double factor = 1 ;
                int k=i-1;
                while(k>=0)//find the Gaussian factor from the upper rows of the current row
                {
                    if(k==i)continue;
                    if(a[k][j]!=0)//if the upper rows same column is not zero
                    {
                        factor = (double)(-a[i][j])/a[k][j];
                        break;
                    }//if
                    k--;
                }//while checking the upper rows of the current row to find the Gaussian factor

                for(int m = 0 ; m<n ; m++)
                {
                    a[i][m] += factor*a[k][m];// Gaussian factor
                }//for
                b[i] += factor*b[k];//do the same thing that we did with A to B
            }//if j<i

        }//i

    }//j

    for(int i=n-1 ; i>=0 ;i--)
    {
        //for example if we have 2*x2 + 3*x3 = b2 we already found x3 the rest is history :)
        double sum = 0 ;
        for(int j = i+1 ; j<n ; j++)
        {
            sum += a[i][j]*x[j];
        }//j
        x[i] = (b[i]-sum)/a[i][i];//calculate x_i --> for example the first loop will find x_n
    }//i



    //output the linear Algebra
    System.out.print("A's matrix after Gaussian:");
    System.out.println();
    for(int row = 0 ; row<n ; row++)
    {
        for(int col = 0 ; col<n ; col++)
        {
            System.out.print(a[row][col]+ " ");
        }
        System.out.println();
    }//i
    System.out.println();
    System.out.print("B's matrix after Gaussian:");
    for(int col = 0 ; col<n ; col++)
    {
        System.out.println(b[col]);
    }//for
    System.out.println();
    System.out.print("x's vector is:");
    for(int col = 0 ; col<n ; col++)
    {
        System.out.println(x[col]);
    }//for

}//linearAlgebra method

如果您需要快速编码，是否有更快的规则，或者高斯规则是最好的编码规则？顺便说一下，这段代码可以帮助那些需要用java计算线性代数的人。该代码已经过测试，但如果有任何错误，请告诉我。

Answer 1

高斯-乔丹消除算法有    时间复杂度。

可以证明，使用 blockwise inversion 的分而治之算法反转 矩阵的运行时间复杂度与内部使用的矩阵乘法算法相同。

因此，如果您实现 Coppersmith–Winograd algorithm对于矩阵乘法，您可以实现的时间复杂度为 或even better .

在您的 中线性系统，一旦找到矩阵逆 矩阵 ，解为 .