количество сложений и умножений при вычислении формул

[st256]

Xaositect в сообщении #242515 писал(а):

Интересно. Я сходу не могу придумать, как это сделать.

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

Примерно так оно и есть.

[Xaositect]

Вы это где-нибудь публиковали? Я не представляю, как делать одно умножение.

[st256]

Xaositect в сообщении #242517 писал(а):

Вы это где-нибудь публиковали? Я не представляю, как делать одно умножение.

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

[Xaositect]

st256 в сообщении #242521 писал(а):

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

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

[maxal]

// тема переезжает в раздел Computer Science, а также приобретает более осмысленный заголовок

[st256]

Xaositect в сообщении #242525 писал(а):

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

Не интересно, потому, что там много сложений. Вроде меньше чем $2N-2$, но все равно много.
К ДПФ его наверное тоже можно применить, только у нас возникает вопрос, а нафиг оно это ДПФ нужно? Не так давно у меня профессор Ланнэ поинтересовался, а как вводить сию нелепицу, как ДПФ? Дело не в том, что Ланнэ не знает, что такое ДПФ. Дело в том, что он СЛИШКОМ хорошо знает, что такое ДПФ

На счет алгоритма, то мы его должны проверить, прежде, чем заявлять, а времени сейчас в обрез. Вы ж, житья со своими хвостами, не даете!

[Xaositect]

st256 в сообщении #242530 писал(а):

На счет алгоритма, то мы его должны проверить, прежде, чем заявлять, а времени сейчас в обрез. Вы ж, житья со своими хвостами, не даете!

Понятно.
Допишете книжку, сообщите, если не трудно.

А про ДПФ зря вы так. В обработке сигналов, обработке изображений, вполне себе применяется на практике.

[st256]

Xaositect в сообщении #242532 писал(а):

st256 в сообщении #242530 писал(а):

На счет алгоритма, то мы его должны проверить, прежде, чем заявлять, а времени сейчас в обрез. Вы ж, житья со своими хвостами, не даете!

Понятно.
Допишете книжку, сообщите, если не трудно.

А про ДПФ зря вы так. В обработке сигналов, обработке изображений, вполне себе применяется на практике.

Мало ли что там применяется на пратике. Вы мне вот скажите, если у Вас есть строго вещественная последовательность длинной $N$, то исходя из теориии информации можно ли обойтись только $N/2$ комплексными членами ДПФ, чтобы сохранить всю информацию о последовательности? Ну чтоб потом можно было вернуться обратно?

[Xaositect]

Вроде бы можно $N/2+1$.
У нас для действительного исходного массива $a$ элементы преобразования Фурье $\sum a_i {\omega}^{ji}$ и $\sum a_i \omega^{-ji}$ будут комплексно-сопряженными.

Можно ли уменьшить до $N/2$ без ущерба скорости алгоритма - не уверен, но скорее всего можно.

[st256]

Xaositect в сообщении #242534 писал(а):

Вроде бы можно $N/2+1$.
У нас для действительного исходного массива $a$ элементы преобразования Фурье $\sum a_i {\omega}^{ji}$ и $\sum a_i \omega^{-ji}$ будут комплексно-сопряженными.

Можно ли уменьшить до $N/2$ без ущерба скорости алгоритма - не уверен, но скорее всего можно.

Можно, можно, хотя неприятности там все-равно будут. Но это уже к вопросу, а как его все-таки вводить. Хотя непрятности там все-равно будут. Кстати, а Вы в курсе, что у последовательностей, спектр ...непериодический на самом деле? Т.е. обоснование алгоритма БПФ накрывается медным тазом

[Xaositect]

st256 в сообщении #242535 писал(а):

Можно, можно. Но это уже к вопросу, а как его все-таки вводить. Кстати, а Вы в курсе, что у последовательностей, спектр ...непериодический на самом деле? Т.е. обоснование алгоритма БПФ накрывается медным тазом

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

[st256]

Xaositect в сообщении #242536 писал(а):

st256 в сообщении #242535 писал(а):

Можно, можно. Но это уже к вопросу, а как его все-таки вводить. Кстати, а Вы в курсе, что у последовательностей, спектр ...непериодический на самом деле? Т.е. обоснование алгоритма БПФ накрывается медным тазом

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

Ну, в принципе можно и не опираться... Но ДПФ это вещь изначально косяная...

[ewert]

Xaositect в сообщении #242536 писал(а):

А что там в БПФ опирается на периодичность?

Быстрота опирается. В лобовом ДПФ порядка $N^2$ операций, а в БПФ -- порядка $N\cdot M$, где $M$ -- сумма сомножителей, на которые раскладывается $N$.

Где-то так, точно не помню... Во всяком случае, будет $N\cdot\log N$ операций, если $N=2^k$.

[Circiter]

Цитата:

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

$y=\sum\limits_{i=1}^{N} a_i x_i $

равно $2N-1$?

Простите, но может кто-нибудь объяснить простому IT'шнику как вообще можно посчитать выражение, содержащее $N-1$ сложений и $N$ умножений, за число операций меньшее чем $2N-1$?

Конечно, если числа в выражении подчиняются некоторым априорно известным функциональным зависимостям, то, очевидно, оптимизация возможна. Действительно, пусть все $a_i$ равны, тогда вынося $a_i$ за "скобки" достаточно будет произвести лишь $N$ операций (кстати, уже в этом случае получается, что изначальное предположение-теоремка неверна, т.е. $2N-1$ не есть минимально возможная оценка...)

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

И ещё, в первоначальной версии заголовка темы упоминалась теория графов, но связь с ней почему-то (почти) не обсуждается... Как переформулировать задачу в терминах этой теории? Картинку, приведенную maxal'ом я что-то не понял. Понял только, что она вроде бы решает или по крайней мере подразумевает задачку экономичного разложения числа на слагаемые, т.е. как бы обратную к исходной (примерно таким способом можно для данного $y$ найти формулу --- суть набор $\{a_i,x_i\}$ --- с минимальным $N$, но по прежнему непонятно как сверхэффективно вычислить формулу по уже имеющимся данным).

В общем, заранее спасибо за ответы...

P.S.: На счет ДПФ. Кажется существуют алгоритмы сложности $O(N)$. Я как-то курил книжку H.J. Nussbaumer, "Fast Fourier Transform and Convolution Algorithms", вот там такой алгоритм предлагался, основанный на гармоническом анализе.

[ewert]

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

P.S.: На счет ДПФ. Кажется существуют алгоритмы сложности $O(N)$.

Не существуют и в принципе не могут существовать. Но существует типа $O(N\log N)$, что ненамного хуже.