быстрый алгоритм вычисления умножения матриц

В середине кода С++, eclipse, мне нужно вычислить умножение матриц A и B с размером 2400 * 3600 (поэтому размеры не совпадают). Матрицы хранятся в двухмерных массивах с плавающей запятой. Они не разрежены, ограничений нет.

Каждое умножение занимает очень много времени (несколько минут), и мне серьезно нужно его уменьшить, потому что у меня есть цикл, который повторяется 50 миллионов раз. и каждый раз новые A и B должны быть умножены. Любые рекомендации приветствуются для уменьшения временной сложности. (даже изменение структуры хранения данных, если вы думаете, что это может помочь). Например, что, если я буду хранить данные в одномерных массивах? Или использовать векторы вместо массивов?

В одном конкретном случае первый столбец всегда равен 1, а значения равны 1, -1 или нулю. Есть идеи для этого случая?
В других случаях значения могут быть любыми. ** одно из этих умножений равно Х, умноженному на его транспонированное. Есть какие-то рекомендации по этому конкретному?


c++ arrays matrix multiplication
person Pegah    schedule 05.06.2011    source источник
comment
Наивный алгоритм общего умножения матриц за O(n^3), но есть способы уменьшить его до O(n^(2.7ish)). Это просто очень большое вычисление, если вы не можете сократить объем работы до того, как начнете. Если большое число возникает из-за согласованного набора преобразований, возможно, вы можете сделать по одному на строку и найти дельты. Или что-то.   -  person dmckee --- ex-moderator kitten    schedule 06.06.2011
comment
Ваши матрицы в основном нули? Если да, то, возможно, вы сможете найти алгоритм умножения, работающий с разреженными матрицами. Разреженная матрица по сути представляет собой карту (i,j)->value.   -  person Emile Cormier    schedule 06.06.2011

Ответы (4)


arrow_upward
13
arrow_downward

Я бы не стал дурачиться, пытаясь написать свой собственный: Google для LAPACK или BLAS, два проверенных временем пакета для численных вычислений, оба оптимизированы до N-й степени. У обоих есть C API, которые вы можете использовать.

person Ernest Friedman-Hill    schedule 05.06.2011
comment
+1: обе библиотеки используют не только оптимизированные алгоритмы, но и оптимизированные реализации, основанные на инструкциях SSE. - person Matthieu M.; 06.06.2011

arrow_upward
9
arrow_downward

Это определенно поможет сохранить вашу вторую матрицу транспонированной, чтобы столбцы совпадали со строками кэша, а не со строками. Разница во времени доступа между кэшем L2 и основной памятью примерно в 10 раз.

person Ben Voigt    schedule 06.06.2011
comment
Хотя кажется вполне очевидным, я не понял, что вы имеете в виду. Не могли бы вы объяснить немного больше? Что, если я действительно хочу умножить A, чтобы транспонировать его? - person Pegah; 06.06.2011
comment
@Pegah: Если вы посмотрите на алгоритм умножения матриц, вы обнаружите, что внутренний цикл выглядит примерно так: sum = 0; for( int k = 0; k < n; ++k ) sum += a[i][k] * b[k][j]; c[i][j] = sum;. Последовательные итерации обращаются к a[i][0], a[i][1], a[i][2], и это нормально, потому что они хранятся рядом друг с другом в памяти, поэтому кеш может считывать большой фрагмент из основной памяти за раз. Но вы также получаете доступ к b[0][j], b[1][j], b[2][j], которые имеют очень плохую локализацию, и кэш должен выполнять много отдельных передач из основной памяти, что очень расточительно. - person Ben Voigt; 07.06.2011

arrow_upward
2
arrow_downward

Вы можете попробовать Eigen.

person genpfault    schedule 06.06.2011

arrow_upward
1
arrow_downward

Если вы говорите о миллионах умножений, первое, что я бы сделал, это обратился бы к чему-то вроде CUDA или DirectCompute, чтобы разгрузить работу графического процессора, который лучше подходит для таких вещей. Это то, что сделал MATLAB, даже если ускорение графического процессора не является обязательным.

Существует множество примеров умножения матриц с ускорением на графическом процессоре, так что ваша работа не должна быть слишком сложной.

person Blindy    schedule 05.06.2011
comment
на самом деле мне нужно сделать это в середине кода С++, и его результаты используются остальной частью кода. так что это не самостоятельная работа. Насколько я понял (только что искал в сети), GPU — это аппаратная реализация, а Directcompute — отдельное приложение. Я ошибаюсь? или я все еще могу использовать GPU в своем коде? - person Pegah; 06.06.2011
comment
Я понятия не имею, о чем вы говорите. CUDA и DirectCompute — это API, которые позволяют вам выполнять арифметические операции на вашем графическом процессоре. Аппаратная реализация чего? В середине кода C++? В отличие от чего?.. - person Blindy; 06.06.2011
comment
@Pegah Да, ваш графический процессор, вероятно, является аппаратной реализацией :) - person Christian Rau; 06.06.2011
comment
@Pegah: GPU означает просто чип процессора на вашей видеокарте. Он очень хорош для выполнения многих одинаковых операций одновременно, но не так хорош для сложных ветвлений. Умножение матриц — это МНОГО одной и той же операции, поэтому она выполняется очень быстро на графическом процессоре. DirectCompute, CUDA и OpenCL — это библиотеки, которые позволяют программе C++ выдавать инструкции вашей видеокарте и перемещать данные туда и обратно. - person Ben Voigt; 06.06.2011