Представление матриц в памяти компьютера: Column Major (Fortran) vs. Row Major (C). Схемы хранения, LAPACK и оптимизация работы с многомерными массивами.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
расположение матриц в памяти компьютеров
the layout of matrices in the memory of computers
Матричное представление — это метод, используемый языком программирования для хранения многомерных матриц, состоящих из столбцов векторов, в памяти. Fortran и C используют различные схемы для своих встроенных массивов. Fortran использует "Column Major" (AoS), при котором все элементы заданного столбца хранятся последовательно в памяти. C использует "Row Major" (SoA), при котором все элементы заданной строки хранятся последовательно в памяти. LAPACK определяет различные матричные представления в памяти. Также существуют представление разреженных матриц и представление матриц в порядке Мортона. Согласно документации, в LAPACK оптимизировано представление унитарных матриц. Некоторые языки, такие как Java, хранят матрицы, используя векторы Iliffe. Они особенно полезны для хранения нерегулярных матриц. Матрицы имеют первостепенное значение в линейной алгебре.
Matrix representation is a method used by a computer language to store column vector matrices of more than one dimension in memory. Fortran and C use different schemes for their native arrays. Fortran uses "Column Major" (AoS), in which all the elements for a given column are stored contiguously in memory. C uses "Row Major" (SoA), which stores all the elements for a given row contiguously in memory. LAPACK defines various matrix representations in memory. There is also Sparse matrix representation and Morton order matrix representation. According to the documentation, in LAPACK the unitary matrix representation is optimized. Some languages such as Java store matrices using Iliffe vectors. These are particularly useful for storing irregular matrices. Matrices are of primary importance in linear algebra.
Основные математические операции
Матрица порядка m × n (читается как m на n) представляет собой набор чисел, расположенных в m строках и n столбцах. Матрицы одинакового порядка можно складывать, складывая соответствующие элементы. Две матрицы можно умножать при условии, что число столбцов первой матрицы равно числу строк второй матрицы. Следовательно, если матрицу m × n умножить на матрицу n × r, то результирующая матрица будет порядка m × r.
An m × n (read as m by n) order matrix is a set of numbers arranged in m rows and n columns. Matrices of the same order can be added by adding the corresponding elements. Two matrices can be multiplied, the condition being that the number of columns of the first matrix is equal to the number of rows of the second matrix. Hence, if an m × n matrix is multiplied with an n × r matrix, then the resultant matrix will be of the order m × r.
На матрицу можно выполнять операции над строками или столбцами, с помощью которых можно получить обратную матрицу. Обратную матрицу также можно получить, определив присоединенную матрицу. Строки и столбцы – это различные виды матриц.
Operations like row operations or column operations can be performed on a matrix, using which we can obtain the inverse of a matrix. The inverse may be obtained by determining the adjoint as well. rows and columns are the different classes of matrices
Рядовой майор (SoA)
При порядке хранения матрицы в стиле "строка за строкой" (row major) векторы легко преобразуются с помощью операций скалярного произведения, поскольку коэффициенты каждого компонента располагаются в памяти последовательно. Следовательно, такая организация данных может быть предпочтительной, если процессор аппаратно поддерживает операции скалярного произведения. Кроме того, становится возможным эффективно использовать аффинную матрицу преобразований "3×4" без добавления отступов или сложных перестановок.
With row major matrix order, it is easy to transform vectors using dot product operations, since the coefficients of each component are sequential in memory. Consequently, this layout may be desirable if a processor supports dot product operations natively. It is also possible to efficiently use a '3×4' affine transformation matrix without padding or awkward permutes.
Колонна майор (AoS)
При использовании порядка столбцов, умножение "матрица на вектор" может быть реализовано с помощью векторизованных операций умножения-сложения, если компоненты вектора транслируются в каждый канал SIMD. Также удобно обращаться к базисным векторам, представленным матрицей преобразования, как к отдельным столбцам, поскольку они располагаются в памяти последовательно.
With column major order, a "matrix × vector" multiply can be implemented with vectorized multiply add operations, if the vector's components are broadcast to each SIMD lane. It is also easy to access the basis vectors represented by a transformation matrix as individual column vectors, as these are contiguous in memory.