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