2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Умножение матриы на вектор
Сообщение21.04.2009, 14:47 
Аватара пользователя
Пусть $A$ --- матрица размерности $n$ на $n$ над полем $GF(q)$, $b$ --- вектор длины $n$ над полем $GF(q)$, $b \ne 0$.
Требуется вычислить $A^ib,\,i=0,1,\ldots,n-1.$ Можно ли это сделать с трудоёмкостью меньшей $O(n^3)?$

 
 
 
 
Сообщение21.04.2009, 15:45 
Аватара пользователя
Можно за $O(n^{\log 7}\log n)$:
Вначале есть вектор $b$
Умножаем его на $A$ и формируем двухстолбцовую матрицу $(b, Ab)$. Вычисляем $A^2$
Умножаем $A^2\cdot(b, Ab)$. Получаем $(A^2b, A^3b)$. Формируем матрицу $(b, Ab, A^2b, A^3b)$. Вычисляем $A^4 = A^2\cdot A^2$.
И так далее.
Если умножать методом Штрассена(он работает над любым полем), то получаем указанную мной оценку.

 
 
 
 
Сообщение21.04.2009, 21:24 
Аватара пользователя
Очень интересный метод!
Но мне необходимо получить оценку не хуже $O(n^2\log n).$ Возможно ли это?

 
 
 
 
Сообщение21.04.2009, 21:32 
Аватара пользователя
Сходу ничего не придумывается, надо лезть в литературу.
А откуда у вас эти $n^2\log n$ взялись? уж очень кажется, что задача связана с возведением матрицы в степень. Возможно, правда, я не в курсе каких-то трюков над конечными полями.

 
 
 
 
Сообщение21.04.2009, 23:31 
Аватара пользователя
Из алгоритма Видемана умножения матриц. Он имеет такую временную сложность, но в нем вычисляются данные произведения.

 
 
 
 Re: Умножение матриы на вектор
Сообщение04.10.2009, 00:26 
Чтобы возвести матрицу в степень, необходимо привести её к Жордановой форме,
для этого нужно сначала привести её ко второй нормальной форме, в которой матрица будет иметь распавшийся вид, после чего каждую клетку привести к Жордановой форме. Потом возвести Жорданову форму(всего лишь надо возвести каждую клетку) в степень. Потом A^m = C * (J^m) * (C^(-1)), где C – матрица перехода к Жордановой форме. Если ещё интересны подробности и обоснования, могу указать первоисточник. Но, алгоритм, предложенный Xaositect, очень красив!

 
 
 
 Re: Умножение матриы на вектор
Сообщение04.10.2009, 03:16 
Господа! Я в растерянности, ведь матрица порядка $n$ умножается на вектор уже за $\mathcal{O}(n^2)$ по определению, а можно и до $\mathcal{O}(n\log n)$ довести без особого труда. Так о чем у вас идет речь??? Объясните пожалуйста.

2Xaositect
Цитата:
Если умножать методом Штрассена

Но ведь этот метод используется для матрично-матричного умножения...


P.S.: Ага, вы имеется ввиду, что умножение над полем Галуа обходится не меньше чем в $\mathcal{O}(n)$? Т.е. таблицу умножения заранее составить в общем случае не получится?

-- Вс окт 04, 2009 11:42:15 --

Тьфу блин, я думал в выражении $A^i b$ символ $i$ -- индекс, а это оказывается степень. Не выспался. :)

 
 
 
 Re: Умножение матриы на вектор
Сообщение04.10.2009, 18:15 
По теме: Возведение в степень кажется может быть выполнено за $\mathcal{O}(\log n)$ матричных умножений. Каждое умножение матриц обходится достаточно дорого, теоретический предел здесь вроде-бы $\mathcal{O}(n^2)$ умножений в конечном поле, но алгоритм Штрассена например дает ещё больше операций, а именно $\mathcal{O}(n^{\log_2 7})$. Умножение итоговой матрицы на вектор потребует в лучшем случае $\mathcal{O}(n\log n)$ умножений. Кстати, возможно ли так эффективно производить матрично-векторное перемножение для произвольных квадратных матриц?

В итоге, количество операций будет порядка $k\log n(n^{\log_2 7}+n)$, где $k$ -- стоимость умножения над $GF(q)$. Кратко эту оценку можно записать (оптимистично положив $k=1$) как $\mathcal{O}(n^{2,4} \log n)$. Получилось почти тоже, что и у Xaositect'а...

2AndreyXYZ
Цитата:
мне необходимо получить оценку не хуже $O(n^2 \log n).$ Возможно ли это?

Да. Теоретически. Алгоритм мне не известен. :)

 
 
 
 Re: Умножение матриы на вектор
Сообщение05.10.2009, 03:36 
Подождите, если вам нужно именно последовательность $A^0 b,\ A^1 b,\ \ldots,\ A^{n-1}b$ вычислить, то это ещё множитель $n$ к сложности приписать придется!

 
 
 
 Re: Умножение матриы на вектор
Сообщение05.10.2009, 19:44 
Хотя не обязательно. Верно ли, что $(AA)b=A(Ab)$ или нет? Если верно, то можно сначала найти $Ab$ с асимптотикой $\mathcal{O}(n\log n)$, а потом последовательно умножать результат на $A$ с той же сложностью.

То есть, что бы построить $\{\mathcal{A}_i\}^{n-1}_{i=0}$, где $$\mathcal{A}_i\equiv\underbrace{A(A(\ldots A(A}_{i}b)))$$ нужно как раз порядка $\mathcal{O}(n^2\log n)$ умножений в $GF(q)$.

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

 
 
 
 Re: Умножение матриы на вектор
Сообщение05.10.2009, 19:50 
Аватара пользователя
Circiter в сообщении #249325 писал(а):
Но я не уверен, что матрично-векторное умножение для квадратных матриц общего вида может быть выполнено всегда значительно дешевле чем за квадратичное время...

Умножение матрицы на вектор над конечным полем - $O(\frac{n^2}{\log n})$ (алгоритм известен как алгоритм четырех русских)

 
 
 
 Re: Умножение матриы на вектор
Сообщение09.10.2009, 03:53 
2AndreyXYZ
Цитата:
Из алгоритма Видемана умножения матриц. Он имеет такую временную сложность, но в нем вычисляются данные произведения.

Может быть объяснения удастся найти в оригинальной работе D.H. Wiedemann, Solving sparse linear equations over finite fields?

 
 
 
 Re: Умножение матриы на вектор
Сообщение11.10.2009, 09:26 
Примечание. Когда я давал оценку с множителем $n^{2,4}$ я кажется немного ошибся. Это для подхода Копперсмита-Винограда выполняется (этот алгоритм закодить сложновато), для Штрассена -- примерно $n^{2,9}$ (хуже).

 
 
 [ Сообщений: 13 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group