Тесты реализации матрицы, я должен взбить себя?

Question

Я пытаюсь найти некоторые тесты умножения / инверсии матриц онлайн. Моя реализация C ++ в настоящее время может инвертировать матрицу 100 x 100 за 38 секунд, но по сравнению с этим тестом, который я обнаружил, производительность моей реализации действительно отстой. Я не знаю, является ли это чем-то сверхоптимизированным или действительно можно легко инвертировать матрицу 200 x 200 примерно за 0,11 секунды, поэтому я ищу дополнительные тесты для сравнения результатов. У тебя есть хорошая связь?

UPDATE Я обнаружил ошибку в своем коде умножения, которая не повлияла на результат, но стала причиной бесполезной траты цикла. Теперь моя инверсия выполняется за 20 секунд. Еще много времени, и любая идея приветствуется.

Спасибо, ребята

Answer 1

Операции такого типа чрезвычайно чувствительны к кешу. Вы хотите выполнять большую часть своей работы над переменными, которые находятся в вашем кеше L1 и L2. Проверьте раздел 6 этого документа:

http://people.redhat.com/drepper/cpumemory.pdf

Он проведет вас через оптимизацию умножения матриц оптимизированным кэш-памятью и получит некоторые значительные улучшения производительности.

Answer 2

Проверьте, передаете ли вы огромные матричные объекты по значению (поскольку это может быть дорогостоящим при копировании всей матрицы).
Если возможно, пройдите по ссылке.

В матрицах и C ++ важно то, что вы хотите избежать максимально возможного копирования.
Таким образом, ваш основной объект, вероятно, не должен содержать «матричные данные», а должен содержать метаданные о матрице и указатель (обернутый чем-то умным) на часть данных. Таким образом, при копировании объекта вы копируете только небольшой фрагмент данных, а не весь объект (см. Пример реализации строки).

Answer 3

Зачем вам нужно реализовывать собственную матричную библиотеку? Как вы уже обнаружили, уже есть чрезвычайно эффективные библиотеки, которые делают то же самое. И как бы людям не хотелось думать о C ++ как о языке производительности, это верно только в том случае, если вы действительно хорошо владеете языком. Чрезвычайно легко писать ужасно медленный код на C ++.

Answer 4

Вы пробовали его профилировать?

После этой бумаги (pdf) для расчета матрицы 100x100 с разложением LU потребуется 1348250 (операции с плавающей запятой). Ядро 2 может делать около 20 Гфлопс ( метрика процессора ). Таким образом, теоретически вы можете сделать инверсию за 1 мс.

Без кода довольно сложно утверждать, что является причиной большого разрыва. Из моего опыта пробной микрооптимизации, такой как циклическое развертывание, кэширование значений, SEE, многопоточность и т. Д., Вы только получите ускорение, которое в лучшем случае является лишь постоянным фактором вашего тока (которого может быть достаточно для вас).

Но если вы хотите увеличить скорость на порядок, вы должны взглянуть на свой алгоритм, возможно, в вашей реализации декомпозиции LU есть ошибка. Еще одно место, на которое стоит обратить внимание - это организация ваших данных, попробуйте другую организацию, соедините элементы строки / столбца.

Answer 5

Я не знаю, супер ли это оптимизировано что-то или, если вы действительно можете легко инвертировать матрицу 200 х 200 примерно 0,11 секунды

MATLAB делает это, не потея ни пота. Реализуете ли вы процедуры LAPACK для инверсии матриц (например, разложение LU)?

Answer 6

Я на самом деле набрал около 7 секунд, используя **double** с вместо **long double** с, но это не так уж много, так как я потерял половину своей точности.

Answer 7

Тесты LINPACK основаны на решении задач линейной алгебры. Они доступны для разных машин и языков . Может быть, они тоже могут вам помочь.

Доступны библиотеки LINPACK C ++ здесь .