Ordinary Least Squares

原始题目：LeetGPU - Ordinary Least Squares

题目描述

在 GPU 上求解普通最小二乘法（OLS）回归问题。给定特征矩阵 $X$（$n\_samples \times n\_features$）和目标向量 $y$（长度 $n\_samples$），计算最小化残差平方和的系数向量 $\beta$：

$$\min_{\beta} \|X\beta - y\|^2$$

OLS 的闭式解为：

$$\beta = (X^T X)^{-1} X^T y$$

实现要求

• 不允许使用外部库。
• solve 函数签名必须保持不变。
• 最终系数必须存储在 beta 向量中。
• 假设特征矩阵 $X$ 满秩（即 $X^T X$ 可逆）。

示例

Input:  X (5 samples × 3 features):
          [[-0.23, -0.23, 1.52],
           [0.77, -0.47, 1.58],
           [-0.14, 0.65, 0.5],
           [-1.91, -1.72, 0.24],
           [-0.46, -0.47, 0.54]]
        y: [83.01, 93.44, 7.33, -62.22, 13.06]
Output: β: [13.97, 29.12, 61.05]

约束条件

• $1 \le n\_samples \le 100{,}000$，$1 \le n\_features \le 1{,}000$。
• $n\_samples \ge n\_features$。
• $-1000.0 \le X, y$ 中的值 $\le 1000.0$。
• 绝对容差 $10^{-2}$，相对容差 $10^{-2}$。
• 性能测试在 $n\_features = 32,\ n\_samples = 32$ 的规模下进行。

解题思路

OLS 求解涉及三步矩阵运算：$X^T X$（Gram 矩阵）、$X^T y$（矩-向量乘）、求解线性方程组。前两步是标准的 GEMM 和 GEMV。第三步是 $n\_features \times n\_features$ 的线性方程组，当 $n\_features$ 较小时（$\le 64$），可以用一个 warp 在共享内存中直接做 Cholesky 分解或 Gauss-Jordan 消元。欢迎在 GitHub Discussions 分享你的解法。