图

SLISC 库简介

   相对于 fortran, 用 C++ 做数值计算的一个缺陷就是语言本身(或标准库)没有矩阵类型(以及高维矩阵类型).

   C++ 的数组只能在 stack 中使用, 而 stack 一般只有即 Mb, 一旦数组太大就会产生 stack overflow 错误. 第二是 stack 中的数据的大小都只能在编译时确定, 所以我们不能在运行是确定数组的长度(例如从文件中读取, 或通过运行时的计算得到).

   之前介绍的 std::vector 可以说是代替数组的最受欢迎的方法.

   理论上我们可以用 vectorvector 的办法定义一个矩阵, 但是这样做数据在内存中是不连续的, 而且 memory allocation 是一个极其耗时的操作(最快的程序时先把所有需要的 memory 都 allocate 好再进行计算).

   更原始(但是效率最高)的办法时干脆不定义矩阵库, 直接用 vector 以及指针, 直接调用 LAPACK 函数进行线性代数运算. 但这样写出的代码难懂, 易错.

   我们希望把矩阵进行一定程度的封装, 但又几乎不损失性能.

   流行的矩阵库, 如 Eigen, 但是代码极其复杂, 错误信息不好懂, 修改起来非常困难.

   Numerical Recipes 中自己定义了简单的矢量和矩阵库, 但是较为简单, 我们就在此基础上自己写一个矩阵库.

   底层用 MKL 来实现, 速度非常快.

   所有的函数都尽量使用指针 interface (因为是最兼容的!最笨的办法往往是最灵活的) 然后可以再封装一层更友好的 interface

   slicing 会有少量的 overhead. 由用户自己权衡是使用 slicing 还是指针 interface.

行主序和列主序

   由于在计算机内存中所有数据都是按顺序排成一行, 所以在储存矩阵时我们就有两种选择, 一是把所有行首尾相接, 叫做行主序(row-major), 二是把所有列首尾相接, 叫列主序(column-major). 例如对于 $2 \times 2$ 的矩阵, 列主序下, 矩阵元在内存中的顺序依次 $(0, 0), (1, 0), (0, 1), (1, 1)$, 而在行主序下顺序为 $(0, 0), (0, 1), (1, 0), (1, 1)$.

   在 fortran 和 Matlab 中1, 语言自带的矩阵都是列主序, 而在 C/C++ 中如果用指针的指针(或数组的数组)来表示矩阵, 得到的将会是行主序. 当然, 由于 C++ 的灵活性, 我们完全可以创造行主序和列主序两种不同的矩阵类.

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

\begin{equation} \leftgroup{ n &= i + N_1 j &\quad &\text{(列主序)}\\ n &= N_2 i + j &\quad &\text{(行主序)} }\end{equation}

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

\begin{equation} \leftgroup{ n &= i_1 + N_1 i_2 + N_1 N_2 i_3 + N_1 N_2 N_3 i_4 &\quad &\text{(列主序)}\\ n &= N_2 N_3 N_4 i_1 + N_3 N_4 i_2 + N_4 i_3 + i_4 &\quad&\text{(行主序)} }\end{equation}
从性能角度来看, 单索引要比多个索引要快.

   至于由单索引计算多索引, 我们可以用整数除法(向下取整) “/” 和求余符号 “%”, 例如对列主序的矩阵有

\begin{equation} \leftgroup{ i &= n \% N\\ j &= n / N }\end{equation}


1. Matlab 最初就是由 fortran 写的

致读者: 小时物理百科一直以来坚持所有内容免费且不做广告,这导致我们处于日渐严重的亏损状态。长此以往很可能会最终导致我们不得不选择商业化,例如大量广告,内容付费,会员制,甚至被收购。因此,我们鼓起勇气在此请求广大读者热心捐款,使网站得以健康发展。如果看到这条信息的每位读者能慷慨捐助 10 元,我们几天内就能脱离亏损状态,并保证网站能在接下来的一整年里向所有读者继续免费提供优质内容。感谢您的支持。
—— 小时(项目创始人)

编辑词条 返回目录 返回主页 捐助项目 © 小时物理百科 保留一切权利