Каков наиболее эффективный способ суммирования ndarray в numpy при минимизации неточности с плавающей запятой?

Question

У меня есть большая матрица со значениями, которые сильно различаются по порядку величины. Чтобы вычислить сумму как можно точнее, мой подход состоял бы в том, чтобы изменить ndarray на 1-мерный массив, отсортировать его и затем добавить его, начиная с наименьших записей. Есть ли лучший/более эффективный способ сделать это?

Answer 1

Я думаю, что при заданных задачах с плавающей запятой наиболее известным алгоритмом для вашей задачи является Kahan summation. Для практических целей суммирование Кахана имеет погрешность, которая не зависит от количества слагаемых, тогда как наивное суммирование имеет погрешность, которая линейно растет с числом слагаемых.

NumPy не использует суммирование Kahan, и нет простого способа его реализации без большого компромисса с производительностью. Но он использует следующую лучшую вещь, pairwise summation, где ошибка растет при некоторых разумных предположениях, как квадратный корень логарифма числа слагаемых.

Поэтому очень вероятно, что Numpy сам по себе уже способен обеспечить достаточно хорошую точность для вашей проблемы. Чтобы проверить это, я бы на самом деле выполнил несколько выборочных случаев с помощью суммирования Кахана (псевдокод в ссылке Википедии выше может быть преобразован тривиально в Python) и считать это как золотой, наилучший возможный результат и сравнить его с:

1. Вызов np.sum на вашей матрице как есть.
2. Вызов np.sum на матрицу после преобразования в 1D, что может дать лучшие результаты, если ваша матрица не смежна в памяти.
3. Вызов np.sum на отсортированную версию массива 1D.

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