Обсуждение участника:Janyell
Добрый день. Подключаюсь к проверке. Статья мне в целом понравилась, и тем больше от этого хочется добавить замечаний, чтобы довести ее до того вида, чтобы она могла остаться на Алговики.
Уважаемые авторы, к Вашей работе есть новые замечания - они для удобства отделены горизонтальной линией от прошлых.
Содержание
1 Пункт 1.1
Разреженная матрица, будучи множеством чисел, не имеющим регулярности, не может быть представлена в памяти машины тем же простым способом, что и полная матрица. Поэтому возникает необходимость дополнительно хранить индексную информацию, указывающую расположение каждого элемента в регулярном массиве.
Что означает фраза, выделенная жирным? Или как-то переформулируйте утверждение, оно не понятно
Однако многие схемы хранения допускают определенную долю нулей, и алгоритм обрабатывает их, как если бы они не были нулями. Тоже непонятно
__
Поправили
Разреженная матрица — матрица с большим количеством нулевых элементов.
Все же матрица с большим количеством нулей может быть сильно плотной и так лучше не писать.
* есть [math]O(n)[/math]. Приведенное определение полезно только для теоретических целей типа попытки оценить асимптотическое поведение алгоритма.
* ограничено в строке, в типичном случае от 2 до 10.
* выражается как [math]n^{1+\gamma}[/math], где [math]\gamma \lt 1[/math].
- Если первое определение подходит только для “теоретического анализа”, то чем лучше третье?
- Второе определение, по-моему, не совсем корректно – оно слишком строгое, не понятно, что за типичный случай, почему именно используется привязка к строкам матрицы, почему именно 2 и 10 (а, например, 1?) и т.д. Есть ли какие-то ссылки на литературу, где такое определение использовалось для анализа или для практических задач? Нужно пояснить смысл такого определения.
Всякую разреженную матрицу можно обрабатывать так, как если бы она была плотной: напротив, всякую плотную, или заполненную, матрицу можно обрабатывать алгоритмами для разреженных матриц.
Как можно обрабатывать плотную матрицу алгоритмами для разреженных матриц, если ее нужно представить в специальном виде?
* сохранять разреженность. Хороший алгоритм для разреженных матриц пытается сохранить разреженность, по возможности уменьшая заполнение.
Это свойство нужно пояснить. Не во всех задачах можно или желательно уменьшать заполнение.
В целях упрощения операций с разреженными матрицами многие алгоритмы разрешают также хранить небольшое количество нулевых элементов и оперировать с ними как с ненулевыми.
Почему именно небольшое количество нулевых элементов?
2 Пункт 1.1.1.1
Поставьте определение ленточной матрицы в начало. Потому что, начиная читать первую фразу, сначала задаешься вопросом, что это такое
__
Поправили
3 Пункт 1.1.1.2
Кроме того, схема является статической, потому что включение нового элемента, лежащего вне оболочки, требует изменения всей структуры (если только не используются записи переменной длины). Также нужны пояснения
__
Поправили
Можно ли описанную схему использовать для хранения несимметричной ленточной матрицы? И общих (необязательно ленточных) симметричных матриц?
4 Пункт 1.1.1.5
Такие неупорядоченные представления могут быть весьма удобны в практических вычислениях. Результаты большинства матричных операций получаются неупорядоченными, а их упорядочение стоило бы значительных затрат машинного времени. В то же время, за немногими исключениями, алгоритмы для разреженных матриц не требуют, чтобы их представления были упорядоченными.
Хорошо бы привести несколько примеров операций, для которых неупорядоченные представления дают выигрыш.
Данный формат используется для симметричных и верхних треугольных матриц, у которых большинство диагональных элементов отличны от нуля.
В чем здесь причина требования «большинство диагональных элементов отличны от нуля»? Формат предназначен для только симметричных или только верхних треугольных? Или и для тех и других?
5 Пункт 1.1.1.6
Идея разбиения большой матрицы на подматрицы или блоки возникает естественным образом. С блоками можно обращаться, как если бы они были элементами матрицы, и блочная матрица превращается в матрицу из матриц.
Это не так, поскольку матричные произведения необязательно коммутативны.
Разбиение на блоки играет важную роль в технологии разреженных матриц, потому что многие алгоритмы, сконструированные первоначально для числовых матриц, можно обобщить на случай матриц из матриц. Большая гибкость, связанная с понятием разбиения, может давать определенные вычислительные преимущества.
Хорошо бы пояснить какие вычислительные преимущества это дает.
С другой стороны, разбиение можно рассматривать просто как инструмент управления данными, помогающий организовать обмен информацией между оперативной памятью и внешними запоминающими устройствами.
Нужно подробнее пояснить какие преимущества блочное разбиение дает при организации обменов информации между оперативной памятью и внешними запоминающими устройствами.
Рассмотрим неявную схему хранения, предназначенную главным образом для симметричных матриц с квадратными диагональными блоками.
В чем заключается неявность в такой схеме хранения?
6 Пункт 1.1.2
Достоинство этих процедур, с вычислительной точки зрения, состоит в том, что единственная требуемая матричная операция — это повторное умножение матрицы на последовательность заполненных векторов; сама матрица не меняется. Опять непонятно
__
Не совсем понятно, что именно непонятно. Добавили комментарий
Умножение разреженной матрицы на вектор используется при вычислении векторов Ланцоша, необходимом при итерационном решении линейных уравнений методом сопряженных градиентов, а также при вычислении собственных значений и собственных векторов матрицы.
Умножение разреженной матрицы на вектор используется и во многих других алгоритмах, методах и задачах, чем примечательны именно эти?
Достоинство этих процедур, с вычислительной точки зрения, состоит в том, что единственная требуемая матричная операция — это повторное умножение матрицы на последовательность заполненных векторов; сама матрица не меняется.
Достоинство этих процедур, по сравнению с какими? В некоторых итерационных методах, например, требуется также умножение и транспонированной матрицы на вектор.
Следовательно, наиболее релевантными для этих задач являются статические схемы хранения.
Есть ли такие схемы хранения, которые при выполнении матрично-векторного произведения изменяют матрицу или требуют изменения структуры данных?
7 Пункт 1.3
Почему вычислительное ядро только последовательной версии? Вычислительное ядро (computational kernel) алгоритма - это часть алгоритма, на которую приходится основное время его работы.
__
Поправили
8 Пункт 1.4
Наверное, вопрос в том, что алгоритм делает помимо запуска вычислительных ядер?
__
Присвоение элементам заполненного вектора-столбца [math]c[/math] результатов запуска вычислительных ядер.
9 Пункт 1.5
Как была выбрана форма хранения матрицы? Это нужно прокомментировать
__
Комментарий был ранее, в пункте 1.1.2. Продублировали
10 Пункт 1.6
Для алгоритма умножения разреженной матрицы размером [math]n \times m[/math], представленной в формате RR (C) U, на вектор длины [math]m[/math] в последовательном (наиболее быстром) варианте требуется:
* [math]nz[/math] сложений (вычитаний), * [math]nz[/math] умножений,
Что здесь понимается как «наиболее быстрый вариант»? Есть ли какие-то более медленные альтернативы? Оценка [math]nz[/math] сложений похоже не совсем правильная. Например, сколько нужно сложений для матрицы с одним ненулевым элементом в алгоритме 1.5?
При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности, что ещё больше увеличивает долю умножений и сложений/вычитаний во времени, требуемом для выполнения умножения разреженной матрицы на вектор.
Непонятное предложение. Увеличивается и доля сложений и доля умножений? Что меняется, с точки зрения числа операций, если делать расчет с двойной точностью?
11 Пункт 1.7
Правильно я понимаю, что на рисунке изображено вычисление всего произведения матрицы на вектор? Аналогичные блоки для разных строк. А разве не должен быть рисунок, изображающий ядро (то есть произведение одной строки на вектор)? (я не уверен, поэтому спрашиваю. Возможно, это как-то надо лучше подписать)
__
Нам показалось верным отобразить на рисунке именно параллельную версию, на которой будет видно как и произведение одной строки на вектор, так и вычисление всех элементов. Как следует из определения графа алгоритма, он должен давать удобное представление не только ядра, но и позволять рассмотреть алгоритм с параллельной точки зрения. Внесли небольшое пояснение для рисунка.
12 Пункт 1.8
При классификации по высоте ЯПФ, таким образом, алгоритм умножения разреженной матрицы на вектор относится к алгоритмам с линейной сложностью. При классификации по высоте ЯПФ его сложность также будет линейной.
Два раза повторяется сложность при классификации по высоте ЯПФ
13 Пункт 2.4
Пока пустой?
__
Поправили
Помимо ненулевых элементов нужно указать размерность матрицы и описать матрицу (случайная или нет, если нет, то какая), которая использовалась в экспериментах.
Это объясняется быстрым ростом накладных расходов на организацию параллельного выполнения. Это подтверждает предположение о том, что накладные расходы начинают сильно превалировать над вычислениями.
Хорошо бы поподробнее описать с чем связаны накладные расходы – обращением к файловой системе или межпроцессорными коммуникациями и какого вида.
