Вопрос о производительности: инвертирование массива указателей на месте по отношению к массиву значений

Question

Фон для запроса этого вопроса заключается в том, что я решаю систему линеаризованных уравнений (Ax = b), где A - матрица (обычно размерности меньше 100x100), а x и b - векторы. Я использую прямой метод, означающий, что сначала инвертирую A, затем нахожу решение x = A^(- 1) b. Этот шаг повторяется в итеративном процессе до сближения.

Как я делаю это сейчас, используя матричную библиотеку (MTL4):
Для каждой итерации я скопировать все coeffiecients А (значения), чтобы объект матрицы, а затем инвертировать. Это самый простой и безопасный вариант.

Используя массив указателей вместо:
Для моего конкретного случая, коэффициентов случаться обновляться между каждой итерации. Эти коэффициенты хранятся в разных переменных (некоторые - массивы, некоторые - нет). Будет ли потенциал для увеличения производительности, если я настрою A как массив, содержащий указатели на эти коэффициенты, а затем инвертирует A на месте?

Самое приятное в последнем варианте заключается в том, что как только я установил указатели в A перед первой итерацией, мне не нужно было бы копировать любые значения между последовательными итерациями. Значения, на которые указывает A, будут автоматически обновляться между итерациями.

Таким образом, вопрос о производительности сводится к этому, как я вижу:
- Процесс инверсии матрицы занимает примерно столько же времени, при условии, что удаление ссылок на указатели не дорого.
- Массив указателей не требует дополнительной памяти для матрицы A, содержащей значения.
- Массив опций указателей не должен копировать все значения NxN A между каждой итерацией.
- Значения, которые указываются на массив указателей, обычно не упорядочены в памяти. Надеемся, что все значения лежат относительно близко в памяти, но * A [0] [1], как правило, не рядом с * A [0] [0] и т. Д.

Любые комментарии к этому материалу? Будет ли последнее замечание влиять на производительность отрицательно, таким образом, взвешивая положительные эффекты производительности?

Answer 1

Тест, тест, тест.

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

Некоторых эффектов, чтобы рассмотреть следующие вопросы:

• памяти местонахождение и кэш-эффекты
• Многопоточности эффекты (некоторые алгоритмы, которые являются оптимальными во время работы одноядерного, причина столкновения памяти/выселения кэша, когда используется более чем один сердечник).

Невозможно заменить испытания.

Answer 2

Вот некоторые комментарии:

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

Таким образом, вы получите следующий набор компромиссов, когда вы выбрали решение указателя:

• Коэффициенты, входящие в состав матрицы А не может быть больше не вычисленный асинхронно с матрицей инверсии.
• Либо все коэффициенты должны быть пересчитаны для каждой итерации (при использовании инверсии на месте, что означает, что инвертированная матрица использует ту же память, что и входная матрица), или вам все равно придется использовать матрицу из значений N x N чтобы удерживать результат инверсии.

Answer 3

Здесь вы получаете хорошие ответы. Единственное, что я бы добавил, это некоторый общий опыт работы.

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

Вы не знаете, будет ли основная часть времени потрачена на инверсию матрицы, умножение, копирование матрицы, разыменование или что-то. Люди могут догадываться. Если бы я должен был догадаться, это была бы инверсия матрицы, потому что это 100x100. Однако, что-то еще, что я не могу предположить, может быть даже больше. Угадай очень плохой послужной список, особенно если вы можете просто узнать.

Here's an example of what I mean.