思路

在本题中，向量用粗体符号表示。

假设原始数据点 $x_i$ 在正交系的坐标可以表示为 $\boldsymbol{i}$ ，则目标函数可以表示为

$$ \sum_{\boldsymbol{i},\ \boldsymbol{j}}\boldsymbol{Ch}(\boldsymbol{i}^r,\ \boldsymbol{j}^r) $$

其中，$\boldsymbol{i}^r,\ \boldsymbol{j}^r$ 分别是 $x_i ， x_j$ 的重建坐标，

$$ ⁍ $$

又有

$$ ⁍ $$

其中，$k$ 是每组 $pivots$ 所含点的个数，$d(x, y)$ 是 $x, y$ 两点间的欧几里得距离计算函数。

Windows 系统下, 要查看系统设备信息, 输入 msinfo32

TODO HERE: 尚未完善

王丁的思路

设： $n$ 是坐标点的个数（例如，500）； $\text{dim}$ 是每个坐标点所在的空间的维数（例如，2或4）； $k$ 是每组 $pivots$ 里面的点的个数，例如 2； $d(\boldsymbol{i}, \boldsymbol{j})$ 是 $\boldsymbol{i}$ 点与 $\boldsymbol{j}$ 点在原始正交直角坐标系下的欧几里得距离；

那么，要想加快计算，我们肯定是需要用空间换时间的。

首先，各个数据点，两两之间的正交坐标系下的欧几里得距离肯定得存在一个矩阵 $dist$ （$n\times n$ 形状），$dist[i][j]$ 存放 $d(\boldsymbol{i}, \boldsymbol{j})$ 的数值。

我觉得，只要这里优化一下，速度就能快很多。甚至可以说主要的性能优化应该就是在这里，

因为之后的计算要么是加要么是比大小，不费太多计算力。

补充说明，这里我用 #pragma omp parallel for num_threads(thread_count) 并行化后，可以算的非常快(0.5秒以内，这个函数就完成了)。而且这里是计算了全部的 $n \times n$ 个元素，实际上不需要这么做（原因会在后面说明）

static double* euclidean_distance;
// ... ...
static inline void calcEuclideanDistanceAndStoreInArray() {
		// when adding this pragma, the program can be really fast!
		#pragma omp parallel for num_threads(thread_count)
		for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
						euclidean_distance[i * n + j] = get_distance(i, j);
				}
				// printf("calcEuclideanDistanceAndStoreInArray: %d\\n", i);
		}
}

// calculate the Euclidean distance between two points, in the original coordinate
static inline double get_distance(int id1, int id2) {
    double sum = 0;
    for (int i = 0; i < dim; i++) {
        double diff = get_point_coordinate_of_id_and_dimension(id1, i) - get_point_coordinate_of_id_and_dimension(id2, i);
        sum += diff * diff;
    }
    return sqrt(sum);
}

// return the original Euclidean coordinate of the point
static inline double get_point_coordinate_of_id_and_dimension(int id, int dimension) {
    return points[id * dim + dimension];
}