Обсуждение участника:Сергей

Хорошая работа, но есть несколько замечаний.

1 Пункт 1.1

~ есть O(n). Такое определение подходит разве что для теоретического анализа асимптотических свойств матричных алгоритмов;

~ в каждой строке не превышает 10 в типичном случае;

~ ограничено $n^{1+\gamma}$, где $\gamma \lt 1$.

- Если первое определение подходит только для “теоретического анализа”, то чем лучше третье?

- Второе определение, по-моему, не совсем корректно – оно слишком строгое, не понятно, что за типичный случай, почему именно используется привязка к строкам матрицы, почему именно 10 и т.д. Есть ли какие-то ссылки на литературу, где такое определение использовалось для анализа или для практических задач? Нужно пояснить смысл такого определения.

- В силу того, что определить разреженную матрицу строго не получается, то можно упомянуть то, что разреженными матрицами можно считать именно те, для которых применение специализированных алгоритмов обработки и/или хранения является оправданным (см., например, короткое обсуждение в Gilbert et al., Sparse Matrices in MATLAB: Design and Implementation, 1992)

Огромные разрежённые матрицы часто возникают при решении таких задач, как дифференциальное уравнение в частных производных.

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

Более того, разреженный строчный формат обеспечивает эффективный доступ к строчкам матрицы; доступ к столбцам по прежнему затруднен. Поэтому предпочтительно использовать этот способ хранения в тех алгоритмах, в которых преобладают строчные операции.

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

2 Пункт 1.2

Пусть матрица размером $N\times M$ содержит в себе $NZ$ ненулевых элементов, где $NZ\ll N^2$

Из этого определения можно получить матрицу со всеми ненулевыми элементами при $N \gg M$, тогда $N M \ll N^2$

3 Пункт 1.3

Итого: $NZ$ умножений + $x$ сложений($NZ-N\lt x\lt NZ-1$).

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

4 Пункт 1.6

$\bullet \ x$ сложений($NZ-N\lt x\lt NZ-1$).

См. пункт 1.3

Всего $2NZ$ операций, где $NZ$ - количество ненулевых элементов.

Почему $NZ + x = 2NZ?$

5 Пункт 1.9

Для матрицы размером $N\times M$, содержащей в себе $NZ$ ненулевых элементов, где $NZ\ll N^2$,

См. пункт 1.2

6 Пункт 1.10

Данный алгоритм обладает свойством детерминированности.

Будет ли влиять выполнение свойства ассоциативности для сложения на детерминированность алгоритма?

7 Пункт 2.4

Включает ли численный эксперимент генерацию матрицы? Нужно также указать размерность самой матрицы, помимо числа ненулевых элементов.

Можно заметить небольшой всплеск эффективности при использовании 64 процессоров.

С чем связан этот «всплеск»? С алгоритмом, программой или вычислительной системой?

8 Пункт 2.7

опечатка - ... также математических пакет Matlab имеет собственную реализацию.