Обсуждение участника:Janyell

Добрый день. Подключаюсь к проверке. Статья мне в целом понравилась, и тем больше от этого хочется добавить замечаний, чтобы довести ее до того вида, чтобы она могла остаться на Алговики.

Уважаемые авторы, к Вашей работе есть новые замечания - они для удобства отделены горизонтальной линией от прошлых.

Пункт 1.1

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

Что означает фраза, выделенная жирным? Или как-то переформулируйте утверждение, оно не понятно

Однако многие схемы хранения допускают определенную долю нулей, и алгоритм обрабатывает их, как если бы они не были нулями. Тоже непонятно

__

Поправили

---

Разреженная матрица — матрица с большим количеством нулевых элементов.

Все же матрица с большим количеством нулей может быть сильно плотной и так лучше не писать.

* есть [math]\displaystyle{ O(n) }[/math]. Приве­денное определение полезно только для теоретических целей типа попытки оценить асимптотическое поведение алгоритма.

* ограничено в строке, в типичном случае от 2 до 10.

* выражается как [math]\displaystyle{ n^{1+\gamma} }[/math], где [math]\displaystyle{ \gamma \lt 1 }[/math].

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

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

Всякую разреженную матрицу можно обрабатывать так, как если бы она была плотной: напротив, вся­кую плотную, или заполненную, матрицу можно обрабатывать алгоритмами для разреженных матриц.

Как можно обрабатывать плотную матрицу алгоритмами для разреженных матриц, если ее нужно представить в специальном виде?

* сохранять разреженность. Хоро­ший алгоритм для разреженных матриц пытается сохранить раз­реженность, по возможности уменьшая заполнение.

Это свойство нужно пояснить. Не во всех задачах можно или желательно уменьшать заполнение.

В целях упрощения операций с разреженными матрицами многие алгоритмы разрешают также хранить небольшое количество нулевых элементов и оперировать с ними как с ненулевыми.

Почему именно небольшое количество нулевых элементов?

Пункт 1.1.1.1

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

__

Поправили

Пункт 1.1.1.2

Кроме того, схема является статической, потому что включение нового элемента, лежащего вне оболочки, требует изменения всей структуры (если только не используются записи переменной длины). Также нужны пояснения

__

Поправили

---

Можно ли описанную схему использовать для хранения несимметричной ленточной матрицы? И общих (необязательно ленточных) симметричных матриц?

Пункт 1.1.1.5

---

Такие неупорядоченные представления могут быть весьма удобны в практических вычислениях. Результаты большинства матричных операций получаются неупорядоченными, а их упорядочение стоило бы значительных затрат машинного времени. В то же время, за немногими исключениями, алгоритмы для разреженных матриц не требуют, чтобы их представления были упорядоченными.

Хорошо бы привести несколько примеров операций, для которых неупорядоченные представления дают выигрыш.

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

В чем здесь причина требования «большинство диагональных элементов отличны от нуля»? Формат предназначен для только симметричных или только верхних треугольных? Или и для тех и других?

Пункт 1.1.1.6

---

Идея разбиения большой матрицы на подматрицы или блоки возникает естественным образом. С блоками можно обращаться, как если бы они были элементами матрицы, и блочная матрица превращается в матрицу из матриц.

Это не так, поскольку матричные произведения необязательно коммутативны.

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

Хорошо бы пояснить какие вычислительные преимущества это дает.

С другой стороны, разбиение можно рассматривать просто как инструмент управления данными, помогающий организовать обмен информацией между оперативной памятью и внешними запоминающими устройствами.

Нужно подробнее пояснить какие преимущества блочное разбиение дает при организации обменов информации между оперативной памятью и внешними запоминающими устройствами.

Рассмотрим неявную схему хранения, предназначенную главным образом для симметричных матриц с квадратными диагональными блоками.

В чем заключается неявность в такой схеме хранения?

Пункт 1.1.2

Достоинство этих процедур, с вычислительной точки зрения, состоит в том, что единственная требуемая матрич­ная операция — это повторное умножение матрицы на последо­вательность заполненных векторов; сама матрица не меняется. Опять непонятно

__

Не совсем понятно, что именно непонятно. Добавили комментарий

---

Умножение разреженной матрицы на вектор используется при вычислении векторов Ланцоша, необходимом при итерационном решении линейных уравнений методом сопряженных градиентов, а также при вычислении собственных значений и собственных векторов матрицы.

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

Достоинство этих процедур, с вычислительной точки зрения, состоит в том, что единственная требуемая матрич­ная операция — это повторное умножение матрицы на последо­вательность заполненных векторов; сама матрица не меняется.

Достоинство этих процедур, по сравнению с какими? В некоторых итерационных методах, например, требуется также умножение и транспонированной матрицы на вектор.

Следовательно, наиболее релевантными для этих задач являются статические схемы хранения.

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

Пункт 1.3

Почему вычислительное ядро только последовательной версии? Вычислительное ядро (computational kernel) алгоритма - это часть алгоритма, на которую приходится основное время его работы.

__

Поправили

Пункт 1.4

Наверное, вопрос в том, что алгоритм делает помимо запуска вычислительных ядер?

__

Присвоение элементам заполненного вектора-столбца [math]\displaystyle{ c }[/math] результатов запуска вычислительных ядер.

Пункт 1.5

Как была выбрана форма хранения матрицы? Это нужно прокомментировать

__

Комментарий был ранее, в пункте 1.1.2. Продублировали

Пункт 1.6

---

Для алгоритма умножения разреженной матрицы размером [math]\displaystyle{ n \times m }[/math], представленной в формате RR (C) U, на вектор длины [math]\displaystyle{ m }[/math] в последовательном (наиболее быстром) варианте требуется:

* [math]\displaystyle{ nz }[/math] сложений (вычитаний), * [math]\displaystyle{ nz }[/math] умножений,

Что здесь понимается как «наиболее быстрый вариант»? Есть ли какие-то более медленные альтернативы? Оценка [math]\displaystyle{ nz }[/math] сложений похоже не совсем правильная. Например, сколько нужно сложений для матрицы с одним ненулевым элементом в алгоритме 1.5?

При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности, что ещё больше увеличивает долю умножений и сложений/вычитаний во времени, требуемом для выполнения умножения разреженной матрицы на вектор.

Непонятное предложение. Увеличивается и доля сложений и доля умножений? Что меняется, с точки зрения числа операций, если делать расчет с двойной точностью?

Пункт 1.7

Правильно я понимаю, что на рисунке изображено вычисление всего произведения матрицы на вектор? Аналогичные блоки для разных строк. А разве не должен быть рисунок, изображающий ядро (то есть произведение одной строки на вектор)? (я не уверен, поэтому спрашиваю. Возможно, это как-то надо лучше подписать)

__

Нам показалось верным отобразить на рисунке именно параллельную версию, на которой будет видно как и произведение одной строки на вектор, так и вычисление всех элементов. Как следует из определения графа алгоритма, он должен давать удобное представление не только ядра, но и позволять рассмотреть алгоритм с параллельной точки зрения. Внесли небольшое пояснение для рисунка.

Пункт 1.8

---

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

Два раза повторяется сложность при классификации по высоте ЯПФ

Пункт 2.4

Пока пустой?

__

Поправили

---

Помимо ненулевых элементов нужно указать размерность матрицы и описать матрицу (случайная или нет, если нет, то какая), которая использовалась в экспериментах.

Это объясняется быстрым ростом накладных расходов на организацию параллельного выполнения. Это подтверждает предположение о том, что накладные расходы начинают сильно превалировать над вычислениями.

Хорошо бы поподробнее описать с чем связаны накладные расходы – обращением к файловой системе или межпроцессорными коммуникациями и какого вида.