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

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

1 Пункт 1.1

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

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

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

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

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

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

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

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

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

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

2 Пункт 1.2

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

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

3 Пункт 1.3

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

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

4 Пункт 1.6

[math]\bullet \ x[/math] сложений([math]NZ-N\lt x\lt NZ-1[/math]).

См. пункт 1.3

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

Почему [math]NZ + x = 2NZ?[/math]

5 Пункт 1.9

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

См. пункт 1.2

6 Пункт 1.10

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

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

7 Пункт 2.4

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

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

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

8 Пункт 2.7

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