计算科学 - 随机稀疏矩阵的乘法 - 吾爱随笔录

随机稀疏矩阵的乘法

计算科学稀疏矩阵矩阵

2021-11-29 08:49:08

我得到了 2 个非结构化（即不具有任何特殊的稀疏模式，如带状/三角形/等）稀疏矩阵 $A$ 和 $B$ 维度（ $n$ X $n$ ) 和密度 $d$ 每个（因此每个矩阵包含 $n^2 d$ 非零元素）。
就概率而言，对于任何元素 $A(i,j)$ ,
$p (A[i,j] \neq 0) = d$ 并且独立于所有其他元素 $A$ .
类似的概率分布发生在 $B$ .
我想知道是否可以计算出预期的密度 $C = AB$ 按照 $n$ 和 $d$ 即分布 $p( C[i,j] \neq 0 )$ ?

1个回答

我对此进行了尝试，希望我能够正确地编写此代码以阐明逻辑。在这个逻辑中，我假设从 $A$ 和 $B$ 用于计算一个术语 $C$ 不能抵消等于 $0$ 而那个 $C$ 基于稀疏性只有零项 $A$ 和 $B$ . 如果您发现任何错误，请告诉我。

\begin{aligned} p ({C (i, j) \neq 0}) & = p (⋃_{k = 1}^{n} {A (i, k) B (k, j) \neq 0}) \\ = 1 - p (⋂_{k = 1}^{n} {A (i, k) B (k, j) \neq 0}^{c}) \\ = 1 - \prod_{k = 1}^{n} p ({A (i, k) B (k, j) \neq 0}^{c}) \\ = 1 - \prod_{k = 1}^{n} (1 - p ({A (i, k) B (k, j) \neq 0})) \\ = 1 - \prod_{k = 1}^{n} (1 - p ({{A (i, k) \neq 0} ⋂ {B (k, j) \neq 0}})) \\ = 1 - \prod_{k = 1}^{n} (1 - p ({A (i, k) \neq 0}) p ({B (k, j) \neq 0})) \\ = 1 - \prod_{k = 1}^{n} (1 - d^{2}) \\ = 1 - {(1 - d^{2})}^{n} \\ \approx n d^{2} \forall d^{2} ≪ 1 \end{aligned}

$\begin{align} p\left( \left\{C(i,j) \neq 0\right\} \right) &= p\left( \bigcup_{k=1}^{n} \left\{ A(i,k)B(k,j) \neq 0 \right\} \right)\\ &= 1 - p\left( \bigcap_{k=1}^{n} \left\{ A(i,k)B(k,j) \neq 0 \right\}^c \right)\\ &= 1 - \prod_{k=1}^n p\left( \left\{ A(i,k)B(k,j) \neq 0 \right\}^c \right)\\ &= 1 - \prod_{k=1}^n \left( 1 - p\left( \left\{ A(i,k)B(k,j) \neq 0 \right\} \right) \right)\\ &= 1 - \prod_{k=1}^n \left( 1 - p\left( \left\{ \left\{A(i,k) \neq 0 \right\} \bigcap \left\{ B(k,j) \neq 0 \right\} \right\} \right) \right)\\ &= 1 - \prod_{k=1}^n \left( 1 - p\left( \left\{A(i,k) \neq 0 \right\} \right) p\left(\left\{ B(k,j) \neq 0 \right\} \right) \right)\\ &= 1 - \prod_{k=1}^n \left( 1 - d^2 \right)\\ &= 1 - \left( 1 - d^2 \right)^n\\ &\approx nd^2\;\;\;\;\; \forall d^2 \ll 1 \end{align}$

其它你可能感兴趣的问题

上一篇龙格-库塔稳定区下一篇刚体旋转如何影响模拟结果？