数据结构：密矩阵

贡献者： addis

　　 一般来说，矩阵的每个元在计算机内存中逐个储存，这种数据结构通常叫做密矩阵（dense matrix）。由于在计算机内存中所有数据都是按顺序排成一行，所以在储存矩阵时我们就有两种选择，一是把矩阵所有行首尾相接，叫做行主序（row-major），二是把矩阵所有列首尾相接，叫列主序（column-major）。例如对于 $2 \times 2$ 的矩阵 $ \boldsymbol{\mathbf{A}} $，列主序下，矩阵元在内存中的顺序依次 $A_{11}, A_{21}, A_{12}, A_{22}$，而在行主序下顺序为 $A_{11},A_{12},A_{21},A_{22}$。

　　 在 Fortran 和 Matlab 中¹，语言自带的矩阵都是列主序。但 C++ 并没有自带的矩阵类型，由于 C++ 的灵活性，我们完全可以创造行主序和列主序两种不同的矩阵类。由于 C++ 的数组的指标从 0 开始，那么矩阵的行标和列表也习惯从 0 开始。

　　 注意有一些代码中为了省事直接用两个 std::vector 嵌套来表示矩阵，例如 vector<vector<int>> a，这样矩阵元就可以用 a[i][j] 表示。但这样得到的并不是密矩阵（小时百科中我们只把上面描述的数据结构叫做密矩阵），因为矩阵每一行都独立进行内存分配，使得每一行第一个元素在内存中并不是紧接着上一行最后一个元素。我们不推荐这种做法，主要是因为普遍使用的 BLAS、Lapack 以及很多科学计算库只支持上面介绍的数据结构。

1. 单索引和双索引的转换

　　 在我们用双索引寻找矩阵元时，我们需要先将其转换为单索引。假设矩阵尺寸为 $N_1 \times N_2$，那么

　　 行主序和列主序也可以延申至高维矩阵，如果使用列主序，那么当我们在内存中按顺序读取数据的时候，第 1 个索引（index）将变化得最快，第 2 个索引变化得第二快，最后得索引变化得最慢。行主序则相反，最后的索引变化得最快，而第一个最慢。例如 4 维数组的多索引变为单索引的公式为

　　 若要由单索引计算多索引，我们可以用整数除法（向下取整）/ 和求余运算 %，例如对列主序的矩阵有

　　 小时百科的 SLISC 库中提供了 C++ 的密矩阵类，详见 “SLISC 的密矩阵类”。

2. 密矩阵的切割

　　 有时候我们希望仅对密矩阵的一个子矩阵进行操作，但为了提高性能又不希望把它重新复制到一个新的密矩阵中。

　　 列主序：

　　 当子矩阵就是大矩阵本身时，$N_{lda}$ 就是行数（列主序）或者列数（行主序）。

1. ^ Matlab 最初就是由 fortran 编写的。