IBM Ponder This #301 · 2023 年 5 月

Lorenzo Gianferrari Pini 与 Radu-Alexandru Todor 提出了这个问题。向量 $x\in {\mathbb{R}}^n$ 长度为 $n$，分量为 $(x_0,x_1,\dots ,x_{n-1})$；$A\in {\mathbb{R}}^{n\times n}$ 是 $n\times n$ 矩阵，要求计算 $x^{T}Ax$。

$x$ 在 $-1$ 与 $1$ 之间等间距取值，例如 $n=5$ 时 $x=(-1,-0.5,0,0.5,1)$。

生成矩阵 $A$ 的方法如下。给定 $k\in \mathbb{N}$，令 $a\in {\mathbb{R}}^{2^k}$ 从 $0$ 至 $1$ 等间距排列，即 $a_t=\frac{t}{2^k-1}$，$t=0,1,\dots ,2^k-1$。矩阵 $A$ 的元素从 $a$ 中取。

给出序列 $Q_0,Q_1,\dots ,Q_{n-1}$，每个 $Q_i\in {\mathbb{N}}^k$ 含 $k$ 个自然数。对两向量定义长度为 $k$ 的比特向量 $Q_i==Q_j$：$Q_i,Q_j$ 的对应分量相等时为 1，否则为 0。令 $[Q_i==Q_j]$ 为该向量 $Q_i==Q_j$ 表示的整数，下标 0 为最低位。

例如 $Q_i=(1,5,7,8)$ 与 $Q_j=(2,5,6,8)$ 得到 $Q_i==Q_j=(0,1,0,1)$，所以 $[Q_i==Q_j]$=$10$，因为 $(0,1,0,1)$ 对应二进制 1010。定义 $A_{ij}=a_{[Q_i==Q_j]}$，即 $A_{ij}$ 根据 $Q_i$、$Q_j$ 的相似性，从固定的 $2^k$ 个值中选择。

$Q_i$ 按下式生成：$Q_i[t]=\lfloor 2^k\cdot (\sin ((i+1)\cdot (t+1))-\lfloor \sin ((i+1)\cdot (t+1))\rfloor )\rfloor$。例如 $k=5$ 时，$Q_{13}=(31,8,2,15,24)$。

任务：对 $k=5,n=2^{20}$ 求 $x^{T}Ax$，四舍五入到三位小数。

附加问题：对 $k=5,n=2^{30}$ 求 $x^{T}Ax$，同样保留三位小数。

解答

认真尝试后再打开

待补充。