Обсуждение участника:Blizn: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
 
(не показано 5 промежуточных версий этого же участника)
Строка 14: Строка 14:
 
- Второе определение, по-моему, не совсем корректно – оно слишком строгое, не понятно, что за типичный случай, почему именно используется привязка к строкам матрицы, почему именно 10 и т.д. Есть ли какие-то ссылки на литературу, где такое определение использовалось для анализа или для практических задач? Нужно пояснить смысл такого определения.  
 
- Второе определение, по-моему, не совсем корректно – оно слишком строгое, не понятно, что за типичный случай, почему именно используется привязка к строкам матрицы, почему именно 10 и т.д. Есть ли какие-то ссылки на литературу, где такое определение использовалось для анализа или для практических задач? Нужно пояснить смысл такого определения.  
  
 +
'''В качестве теоретической основы использовался Писсанецки, ссылка на него указана выше в статье. Текст использовался именно оттуда, ничего своего я не придумывала. Почему именно 10? Потому что, как было сказано, НЕЛЬЗЯ дать строгого определения тому, начиная с какого количества элементов матрица перестаёт быть плотной и начинает считаться разреженной. А значит, что нельзя сказать, что запрещено определить матрицу именно так. По этой же причине ни одно определение не хуже и не лучше, они просто даны разными людьми в попытках дать более строгое определение, чем просто "много нулей".'''
  
 
== Пункт 1.1.1.1 ==
 
== Пункт 1.1.1.1 ==
Строка 20: Строка 21:
 
'''В данном формате вместо одного двумерного массива, используются три одномерных.'''
 
'''В данном формате вместо одного двумерного массива, используются три одномерных.'''
  
−
Плотную матрицу можно представить и, например, в виде одномерного массива. Тогда получается обычный формат хранения лучше?  
+
Плотную матрицу можно представить и, например, в виде одномерного массива. Тогда получается обычный формат хранения лучше?
  
 +
'''В данном формате не приходится хранить нули, только значимые коэффициенты, так что обычный формат хранения лучше, когда значимых коэффициентов много. Что значит "много" - указано далее по статье.'''
  
 
== Пункт 1.1.1.2 ==
 
== Пункт 1.1.1.2 ==
Строка 37: Строка 39:
  
 
Умножение разреженной матрицы на вектор используется и во многих других алгоритмах, методах и задачах, чем примечательны именно эти?
 
Умножение разреженной матрицы на вектор используется и во многих других алгоритмах, методах и задачах, чем примечательны именно эти?
 +
 +
'''Это просто примеры, и рассмотрение их значимости и примечательности не относится к теме разреженных матриц.'''
  
  
Строка 43: Строка 47:
 
Достоинство этих процедур, по сравнению с какими? В некоторых итерационных методах, например, требуется также умножение и транспонированной матрицы на вектор.
 
Достоинство этих процедур, по сравнению с какими? В некоторых итерационных методах, например, требуется также умножение и транспонированной матрицы на вектор.
  
 +
'''Достоинство по сравнению с теми, для которых повторное умножение матрицы на последовательность заполненных векторов не является единственной требуемой матричной операцией.'''
  
 
== Пункт 1.6 ==
 
== Пункт 1.6 ==
Строка 56: Строка 61:
 
Что здесь понимается как «наиболее быстрый вариант»? Есть ли какие-то более медленные альтернативы? Оценка <math>l</math> сложений похоже не совсем правильная. Например, сколько нужно сложений для матрицы с одним ненулевым элементом в алгоритме 1.5?
 
Что здесь понимается как «наиболее быстрый вариант»? Есть ли какие-то более медленные альтернативы? Оценка <math>l</math> сложений похоже не совсем правильная. Например, сколько нужно сложений для матрицы с одним ненулевым элементом в алгоритме 1.5?
  
 +
'''Медленные альтернативы есть везде. Ту же сортировку можно делать обезьянью, а можно сортировать qsort'ом.'''
  
 
== Пункт 1.8 ==
 
== Пункт 1.8 ==
Строка 62: Строка 68:
 
Можно ли записать параллельный алгоритм, использующий больше чем n процессоров, где n - число строк(столбцов)?
 
Можно ли записать параллельный алгоритм, использующий больше чем n процессоров, где n - число строк(столбцов)?
  
 +
'''Можно, но не имеет смысла. Как было указано ниже в пункте 2.4 при большом количестве процессоров и малом количестве данных основные временные затраты приходятся именно на пересылки, а не на вычисления, поэтому логично свести их к минимуму. При увеличении числа процессоров число пересылок только увеличится и, разумеется, программа станет работать только дольше.'''
  
 
== Пункт 1.10 ==
 
== Пункт 1.10 ==
Строка 75: Строка 82:
  
 
Нужно явно написать в тексте, что рассматривался целочисленный алгоритм. Почему не вещественное матрично-векторное умножение? Приводимые оценки для числа операций алгоритма (п.1.6, 1.8) разве учитывают вспомогательные целочисленные операции, например, для организации циклов?
 
Нужно явно написать в тексте, что рассматривался целочисленный алгоритм. Почему не вещественное матрично-векторное умножение? Приводимые оценки для числа операций алгоритма (п.1.6, 1.8) разве учитывают вспомогательные целочисленные операции, например, для организации циклов?
 +
 +
'''Конечно нет, потому что всё это - особенности реализации, зависящие от неё (там же не учитывается время на пересылки, время на вывод данных, на их считывание и так далее). Описание алгоритма не зависит от реализации. Если речь идёт в вычисление "старта" и количестве элементов в строке - это аналог вычисление IAA и IAB, на которые слишком малочисленны, а в пункте 1.6 указано, что "Умножения и сложения составляют основную часть алгоритма."'''
 +
 +
'''Целочисленное - потому что захотелось и лично мне так было удобнее при ручном тестировании правильности работы кода. Везде, где идёт определение элементов матрицы и вектора, можно заменить int на double, я считаю, этот вопрос не является принципиальным.'''
  
  
Строка 81: Строка 92:
 
Здесь размер матрицы – это число ненулевых элементов? Нужно привести и размер матрицы, и число ненулевых элементов.
 
Здесь размер матрицы – это число ненулевых элементов? Нужно привести и размер матрицы, и число ненулевых элементов.
  
 +
'''Здесь размер матрицы - это её размерность. Матрицы генерировались случайно, а данные стёрты и восстановить их невозможно, а значит я не могу указать точно, сколько именно было ненулевых элементов. Впрочем, из генератора видно, что число нулевых и ненулевых элементов было где-то 50/50.'''
  
 
Какая структура матрицы, которая использовалась в экспериментах? Какова доля операций чтения из файла в экспериментах?
 
Какая структура матрицы, которая использовалась в экспериментах? Какова доля операций чтения из файла в экспериментах?
  
−
 
+
'''Что значит "структура матрицы"? Матрица, как я и писала, генерировалась случайно с помощью функций языка Python. Что же касается чтения в самом начале указано, что каждый процессор считает кусок данных, предоставленных ему. Происходит это 1 раз и в самом начале.'''
−
 
 
  
 
== Статья [[Участник:Blizn/Хранение ненулевых элементов разреженной матрицы. Умножение разреженной матрицы на вектор.]] ==
 
== Статья [[Участник:Blizn/Хранение ненулевых элементов разреженной матрицы. Умножение разреженной матрицы на вектор.]] ==

Текущая версия на 16:57, 2 декабря 2016

--Evgeny Mortikov (обсуждение) 02:50, 2 декабря 2016 (MSK) К Вашей работе есть несколько замечаний по содержанию.

1 Пункт 1.1

--Evgeny Mortikov (обсуждение) 02:50, 2 декабря 2016 (MSK)

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

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

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

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

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

В качестве теоретической основы использовался Писсанецки, ссылка на него указана выше в статье. Текст использовался именно оттуда, ничего своего я не придумывала. Почему именно 10? Потому что, как было сказано, НЕЛЬЗЯ дать строгого определения тому, начиная с какого количества элементов матрица перестаёт быть плотной и начинает считаться разреженной. А значит, что нельзя сказать, что запрещено определить матрицу именно так. По этой же причине ни одно определение не хуже и не лучше, они просто даны разными людьми в попытках дать более строгое определение, чем просто "много нулей".

2 Пункт 1.1.1.1

--Evgeny Mortikov (обсуждение) 02:50, 2 декабря 2016 (MSK)

В данном формате вместо одного двумерного массива, используются три одномерных.

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

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

3 Пункт 1.1.1.2

--Evgeny Mortikov (обсуждение) 02:50, 2 декабря 2016 (MSK)

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

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


4 Пункт 1.1.2

--Evgeny Mortikov (обсуждение) 02:50, 2 декабря 2016 (MSK)

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

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

Это просто примеры, и рассмотрение их значимости и примечательности не относится к теме разреженных матриц.


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

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

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

5 Пункт 1.6

--Evgeny Mortikov (обсуждение) 02:50, 2 декабря 2016 (MSK)

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

[math]l[/math] сложений,

[math]l[/math] умножений.


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

Медленные альтернативы есть везде. Ту же сортировку можно делать обезьянью, а можно сортировать qsort'ом.

6 Пункт 1.8

--Evgeny Mortikov (обсуждение) 02:50, 2 декабря 2016 (MSK)

Можно ли записать параллельный алгоритм, использующий больше чем n процессоров, где n - число строк(столбцов)?

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

7 Пункт 1.10

--Evgeny Mortikov (обсуждение) 02:50, 2 декабря 2016 (MSK)

Таким образом хранение в формате RR(C) не является эффективным для матриц, в которых [math]l \gt \frac{xnm - y(n+1)}{x+y}[/math].

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


8 Пункт 2.4

--Evgeny Mortikov (обсуждение) 02:50, 2 декабря 2016 (MSK)

Нужно явно написать в тексте, что рассматривался целочисленный алгоритм. Почему не вещественное матрично-векторное умножение? Приводимые оценки для числа операций алгоритма (п.1.6, 1.8) разве учитывают вспомогательные целочисленные операции, например, для организации циклов?

Конечно нет, потому что всё это - особенности реализации, зависящие от неё (там же не учитывается время на пересылки, время на вывод данных, на их считывание и так далее). Описание алгоритма не зависит от реализации. Если речь идёт в вычисление "старта" и количестве элементов в строке - это аналог вычисление IAA и IAB, на которые слишком малочисленны, а в пункте 1.6 указано, что "Умножения и сложения составляют основную часть алгоритма."

Целочисленное - потому что захотелось и лично мне так было удобнее при ручном тестировании правильности работы кода. Везде, где идёт определение элементов матрицы и вектора, можно заменить int на double, я считаю, этот вопрос не является принципиальным.


размер матрицы [1000 : 10000] с шагом 1000.

Здесь размер матрицы – это число ненулевых элементов? Нужно привести и размер матрицы, и число ненулевых элементов.

Здесь размер матрицы - это её размерность. Матрицы генерировались случайно, а данные стёрты и восстановить их невозможно, а значит я не могу указать точно, сколько именно было ненулевых элементов. Впрочем, из генератора видно, что число нулевых и ненулевых элементов было где-то 50/50.

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

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

9 Статья Участник:Blizn/Хранение ненулевых элементов разреженной матрицы. Умножение разреженной матрицы на вектор.

9.1 Отсутствующие части

9.2 Замечания по тексту

Источник — https://algowiki-project.org/w/ru/index.php?title=Обсуждение_участника:Blizn&oldid=19882