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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 1: Строка 1:
 +
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 02:50, 2 декабря 2016 (MSK) К Вашей работе есть несколько замечаний по содержанию.
 +
 +
== Пункт 1.1 ==
 +
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 02:50, 2 декабря 2016 (MSK)
 +
 +
'''- есть <math>O(n)</math>. Такое определение подходит разве что для теоретического анализа асимптотических свойств матричных алгоритмов;'''
 +
 +
'''- в каждой строке не превышает 10 в типичном случае;'''
 +
 +
'''- ограничено <math>n^{1+\gamma}</math>, где <math>\gamma < 1</math>.'''
 +
 +
- Если первое определение подходит только для “теоретического анализа”, то чем лучше третье?
 +
 +
- Второе определение, по-моему, не совсем корректно – оно слишком строгое, не понятно, что за типичный случай, почему именно используется привязка к строкам матрицы, почему именно 10 и т.д. Есть ли какие-то ссылки на литературу, где такое определение использовалось для анализа или для практических задач? Нужно пояснить смысл такого определения.
 +
 +
 +
== Пункт 1.1.1.1 ==
 +
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 02:50, 2 декабря 2016 (MSK)
 +
 +
'''В данном формате вместо одного двумерного массива, используются три одномерных.'''
 +
 +
Плотную матрицу можно представить и, например, в виде одномерного массива. Тогда получается обычный формат хранения лучше?
 +
 +
 +
== Пункт 1.1.1.2 ==
 +
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 02:50, 2 декабря 2016 (MSK)
 +
 +
'''Такие неупорядоченные представления могут быть очень удобны в практических вычислениях. Результаты большинства матричных операций получаются неупорядоченными, а их упорядочение стоило бы значительных затрат машинного времени. В то же время, за немногими исключениями, алгоритмы для разреженных матриц не требуют, чтобы их представления были упорядоченными.'''
 +
 +
Хорошо бы привести примеры матричных операций, для которых неупорядоченное представление дает выигрыш, по сравнению с упорядоченным.
 +
 +
 +
== Пункт 1.1.2 ==
 +
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 02:50, 2 декабря 2016 (MSK)
 +
 +
'''Важным приложением этих алгоритмов является вычисление векторов Ланцоша, необходимое при итерационном решении линейных уравнений методом сопряженных градиентов, а также при вычислении собственных значений и собственных векторов матрицы.'''
 +
 +
Умножение разреженной матрицы на вектор используется и во многих других алгоритмах, методах и задачах, чем примечательны именно эти?
 +
 +
 +
'''Достоинство этих процедур, с вычислительной точки зрения, состоит в том, что единственная требуемая матричная операция - это повторное умножение матрицы на последовательность заполненных векторов; сама матрица не меняется.'''
 +
 +
Достоинство этих процедур, по сравнению с какими? В некоторых итерационных методах, например, требуется также умножение и транспонированной матрицы на вектор.
 +
 +
 +
== Пункт 1.6 ==
 +
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника: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?
 +
 +
 +
== Пункт 1.8 ==
 +
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 02:50, 2 декабря 2016 (MSK)
 +
 +
Можно ли записать параллельный алгоритм, использующий больше чем n процессоров, где n - число строк(столбцов)?
 +
 +
 +
== Пункт 1.10 ==
 +
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 02:50, 2 декабря 2016 (MSK)
 +
 +
'''Таким образом хранение в формате RR(C) не является эффективным для матриц, в которых <math>l > \frac{xnm - y(n+1)}{x+y}</math>.'''
 +
 +
Нужно уточнить по какому критерию сравнивается «эффективность». Просто занимает меньше памяти? Или, например, сравнивается скорость доступа к памяти или время выполнения матричных операций?
 +
 +
 +
== Пункт 2.4 ==
 +
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 02:50, 2 декабря 2016 (MSK)
 +
 +
Нужно явно написать в тексте, что рассматривался целочисленный алгоритм. Почему не вещественное матрично-векторное умножение? Приводимые оценки для числа операций алгоритма (п.1.6, 1.8) разве учитывают вспомогательные целочисленные операции, например, для организации циклов?
 +
 +
 +
'''размер матрицы [1000 : 10000] с шагом 1000.'''
 +
 +
Здесь размер матрицы – это число ненулевых элементов? Нужно привести и размер матрицы, и число ненулевых элементов.
 +
 +
 +
Какая структура матрицы, которая использовалась в экспериментах? Какова доля операций чтения из файла в экспериментах?
 +
 +
 +
 +
 
== Статья [[Участник:Blizn/Хранение ненулевых элементов разреженной матрицы. Умножение разреженной матрицы на вектор.]] ==
 
== Статья [[Участник:Blizn/Хранение ненулевых элементов разреженной матрицы. Умножение разреженной матрицы на вектор.]] ==
 +
  
 
=== Отсутствующие части ===
 
=== Отсутствующие части ===

Версия 02:53, 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 и т.д. Есть ли какие-то ссылки на литературу, где такое определение использовалось для анализа или для практических задач? Нужно пояснить смысл такого определения.


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?


6 Пункт 1.8

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

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


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) разве учитывают вспомогательные целочисленные операции, например, для организации циклов?


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

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


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



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

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

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

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