Обсуждение участника:Сергей
Хорошая работа, но есть несколько замечаний.
Пункт 1.1
~ есть O(n). Такое определение подходит разве что для теоретического анализа асимптотических свойств матричных алгоритмов;
~ в каждой строке не превышает 10 в типичном случае;
~ ограничено [math]\displaystyle{ n^{1+\gamma} }[/math], где [math]\displaystyle{ \gamma \lt 1 }[/math].
- Если первое определение подходит только для “теоретического анализа”, то чем лучше третье?
- Второе определение, по-моему, не совсем корректно – оно слишком строгое, не понятно, что за типичный случай, почему именно используется привязка к строкам матрицы, почему именно 10 и т.д. Есть ли какие-то ссылки на литературу, где такое определение использовалось для анализа или для практических задач? Нужно пояснить смысл такого определения.
- В силу того, что определить разреженную матрицу строго не получается, то можно упомянуть то, что разреженными матрицами можно считать именно те, для которых применение специализированных алгоритмов обработки и/или хранения является оправданным (см., например, короткое обсуждение в Gilbert et al., Sparse Matrices in MATLAB: Design and Implementation, 1992)
Огромные разрежённые матрицы часто возникают при решении таких задач, как дифференциальное уравнение в частных производных.
Это предложение нужно переформулировать. Разреженные матрицы часто возникают при решении дифференциальных уравнений именно численными методами.
Более того, разреженный строчный формат обеспечивает эффективный доступ к строчкам матрицы; доступ к столбцам по прежнему затруднен. Поэтому предпочтительно использовать этот способ хранения в тех алгоритмах, в которых преобладают строчные операции.
Что здесь понимается под эффективностью доступа к строкам матрицы и тем, что доступ к столбцам затруднен? Если речь идет об устройстве компьютерной памяти, то это нужно пояснить, поскольку до этого в разделе описывается просто структура данных.
Пункт 1.2
Пусть матрица размером [math]\displaystyle{ N\times M }[/math] содержит в себе [math]\displaystyle{ NZ }[/math] ненулевых элементов, где [math]\displaystyle{ NZ\ll N^2 }[/math]
Из этого определения можно получить матрицу со всеми ненулевыми элементами при [math]\displaystyle{ N \gg M }[/math], тогда [math]\displaystyle{ N M \ll N^2 }[/math]
Пункт 1.3
Итого: [math]\displaystyle{ NZ }[/math] умножений + [math]\displaystyle{ x }[/math] сложений([math]\displaystyle{ NZ-N\lt x\lt NZ-1 }[/math]).
Оценка для операций сложения здесь не до конца правильная (например, если матрица нулевая). Лучше оценку записать в форме равенства. Или вообще не рассматривать случай нулевых строк.
Пункт 1.6
[math]\displaystyle{ \bullet \ x }[/math] сложений([math]\displaystyle{ NZ-N\lt x\lt NZ-1 }[/math]).
См. пункт 1.3
Всего [math]\displaystyle{ 2NZ }[/math] операций, где [math]\displaystyle{ NZ }[/math] - количество ненулевых элементов.
Почему [math]\displaystyle{ NZ + x = 2NZ? }[/math]
Пункт 1.9
Для матрицы размером [math]\displaystyle{ N\times M }[/math], содержащей в себе [math]\displaystyle{ NZ }[/math] ненулевых элементов, где [math]\displaystyle{ NZ\ll N^2 }[/math],
См. пункт 1.2
Пункт 1.10
Данный алгоритм обладает свойством детерминированности.
Будет ли влиять выполнение свойства ассоциативности для сложения на детерминированность алгоритма?
Пункт 2.4
Включает ли численный эксперимент генерацию матрицы? Нужно также указать размерность самой матрицы, помимо числа ненулевых элементов.
Можно заметить небольшой всплеск эффективности при использовании 64 процессоров.
С чем связан этот «всплеск»? С алгоритмом, программой или вычислительной системой?
Пункт 2.7
опечатка - ... также математических пакет Matlab имеет собственную реализацию.