基于列的向后替换翻牌计数

Question

我有一个函数正在尝试对进行翻牌计数，但我一直得到 2n 而不是 n^2。我知道它应该是 n^2，因为它仍然是一个 nxn 三角系统，只是按列一阶求解。我是线性代数的新手，所以请原谅我。我将包括函数，以及我尽我所能展示的所有工作。 Column BS Function

function col_bs(U, b)

    n = length(b)
    x = copy(b)

    for j = n:-1:2
        if U[j,j] == 0
            error("Error: Matrix U is singular.")
        end
        x[j] = x[j]/U[j,j] 

        for i=1:j-1
            x[i] = x[i] - x[j] * U[i , j ]
        end
    end

    x[1] = x[1]/U[1,1]


    return x
end

开始2次加法和乘法 []−[]∗[]

循环执行以下操作： ∑=−112

1 次失败 []/=[]
在 for 循环中总共做了： 1+∑=−112
循环本身做： ∑=2(1+∑=−112))
最后翻牌是 [1]=[1]/[1,1].
终于有了 1+(∑=2(1+∑=−112))).

我们现在可以分解。

如果我们分发和简化 1+(∑=2+∑=2∑=−112).

我们可以只看重要的变量而忽略常量，

1+(+(1))(+(1))+2

这意味着如果我们忽略常量，这个公式失败的最高可能性是（这可能暗示我的函数有什么问题，因为它应该是 2 就像我们的其他三角系统一样我相信) Proof

Proof

Answer 1

由于代码有两个嵌套的 for 循环，每个循环都与 n 成正比，因此可以预期二次运行时间。

using LinearAlgebra, BenchmarkTools

function col_bs(U, b)
    n = length(b)
    x = copy(b)
    for j = n:-1:2                          # n*(
        if U[j,j] == 0
            error("Error: Matrix U is singular.")
        end
        x[j] = x[j]/U[j,j]                  #    1 +
        
        for i=1:j-1                         #    n*(
            x[i] = x[i] - x[j] * U[i , j ]  #      2
        end                                 #    )
    end                                     # ) +
    x[1] = x[1]/U[1,1]                      # 1
    return x                                # = n*(1+2*n) + 1 = O(n^2)
end

for n in 2 .^[1:10...]
    local U = triu(randn(n,n))
    local b = randn(n,1)
    @btime col_bs($U, $b)
end

很好地接近预期的 4 倍运行时间增长：

  61.366 ns (1 allocation: 80 bytes)
  90.900 ns (1 allocation: 96 bytes)
  147.557 ns (1 allocation: 128 bytes)
  280.000 ns (1 allocation: 192 bytes)
  1.100 μs (1 allocation: 336 bytes)
  3.900 μs (1 allocation: 576 bytes)
  15.600 μs (1 allocation: 1.06 KiB)
  56.800 μs (1 allocation: 2.12 KiB)
  219.200 μs (1 allocation: 4.12 KiB)
  957.200 μs (1 allocation: 8.12 KiB)

基于列的向后替换翻牌计数

Column Based Backwards Substitution Flop count

python

linear-algebra

julia

jupyter-notebook