Умножение матриы на вектор

[AndreyXYZ]

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

[Xaositect]

Можно за $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$.
И так далее.
Если умножать методом Штрассена(он работает над любым полем), то получаем указанную мной оценку.

[AndreyXYZ]

Очень интересный метод!
Но мне необходимо получить оценку не хуже $O(n^2\log n).$ Возможно ли это?

[Xaositect]

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

[AndreyXYZ]

Из алгоритма Видемана умножения матриц. Он имеет такую временную сложность, но в нем вычисляются данные произведения.

[malin]

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

[Circiter]

Господа! Я в растерянности, ведь матрица порядка $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$ -- индекс, а это оказывается степень. Не выспался.

[Circiter]

По теме: Возведение в степень кажется может быть выполнено за $\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).$ Возможно ли это?

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

[Circiter]

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

[Circiter]

Хотя не обязательно. Верно ли, что $(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)$.

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

[Xaositect]

Circiter в сообщении #249325 писал(а):

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

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

[Circiter]

2AndreyXYZ

Цитата:

Из алгоритма Видемана умножения матриц. Он имеет такую временную сложность, но в нем вычисляются данные произведения.

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

[Circiter]

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