基于列的反向替换函数的数学失败计数（Julia）

Question

我是线性代数的新手，正在学习用 Julia lang 实现的三角系统。我有一个 col_bs() 函数 我会在这里展示我需要做一个数学翻牌计数。它不一定是超级技术，这是为了学习目的。我试图将函数分解为内部 i 循环和外部 j 循环。中间是每个 FLOP 的计数，我认为这是无用的，因为常量通常都会被丢弃。

我也知道答案应该是 N^2，因为它是 正向替换算法的反向版本，即 N^2 触发器。我尽力推导出这个 N^2 计数，但是当我尝试时，我得到了一个奇怪的 Nj 计数。我会尽力提供我所做的所有工作！感谢所有提供帮助的人。

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

1: To start 2 flops for the addition and multiplication x[i] - x[j] * U[i , j ]

The $i$ loop does: $$ \sum_{i=1}^{j-1} 2$$

2: 1 flop for the division $$ x[j]  / = U[j,j] $$
3: Inside the for $j$ loop in total does: $$ 1 + \sum_{i=1}^{j-1} 2$$
4:The $j$ loop itself does:$$\sum_{j=2}^n ( 1 + \sum_{i=1}^{j-1} 2)) $$
5: Then one final flop for $$  x[1] = x[1]/U[1,1].$$

6: Finally we have 
$$\ 1 + (\sum_{j=2}^n ( 1 + \sum_{i=1}^{j-1} 2))) .$$

Which we can now break down.

If we distribute and simplify
$$\ 1 + (\sum_{j=2}^n + \sum_{j=2}^n \sum_{i=1}^{j-1} 2) .$$

We can look at only the significant variables and ignore constants,

$$\
  \ 1 + (n + n(j-1)) 
  \ n + nj - n
  \ nj
$$

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

Answer 1

将您的代码简化为这种形式：

for j = n:-1:2
   ...
   for i = 1:j-1
      ... do k FLOPs
   end
end

内循环需要 k*(j-1) 次失败。因此外循环的成本是

既然知道了j <= n，就知道这个总和还不到(n-1)^2，大O就够了。

不过其实你应该也能想通

基于列的反向替换函数的数学失败计数（Julia）

Mathematical flop count of column based back substitution function ( Julia )

linear-algebra

mathematical-optimization

linear-programming

flops

julia