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

[Xaositect]

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

Ok. И как его использовать? E.g., искать кратчайший путь?

А по разному его использовать можно.
Вот, скажем, у того же преобразования Фурье граф обязан быть суперконцентратором (Граф с $n$ входами и $n$ выходами называется суперконцентратором, если для любых заданных подмножеств из $k$ входов и $k$ выходов ($k<n$) суще­ствует $k$ непересекающихся путей с началами в заданных входах и кон­цами в заданных выходах.) Если бы можно было доказать, что суперконцентратор должен быть достаточно сложным(иметь $n\log n$ вершин), то получилась бы оценка на сложность преобразования Фурье. Но, к сожалению, существуют суперконцентраторы линейной сложности.

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

Двупроходный алгоритм: сначала анализируем данные, выявляя зависимости в этой выборке; а потом используя эти зависисимости упрощаем формулку, что облегчает её вычисление

Ну да, такое иногда используют. В основном в теоретических задачах, но иногда и на практике (так наз. предвычисление, precomputation).

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

Не совсем понимаю, почему в этой теме так много было сказано о свертке и о Фурье-трансформации

Просто это известная и широко исследуемая задача.

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

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

Возможно, но это надо спрашивать у st256. Лично я не верю в линейное кол-во умножений для вычисления свертки.

[Circiter]

2st256
Вот по совету Xaositect'а обращаюсь лично к вам. Вы получили оценку $\approx N$ операций для вычисления той формулы из первого сообщения распределением сложности свертки (например $N^2$ операций) на все отсчеты? То есть $N^2/N=N$? Или не угадал? Заранее благодарю за ответ.

-- Вс сен 13, 2009 19:41:15 --

2Xaositect

Цитата:

Граф с $n$ входами и $n$ выходами называется суперконцентратором, если для любых заданных подмножеств из $k$ входов и $k$ выходов ($k<n$) суще­ствует $k$ непересекающихся путей с началами в заданных входах и кон­цами в заданных выходах.

Простите, но не совсем понял про непересекающиеся пути. То есть граф обязательно планарен? Или подразумевалось отсутствие у путей общих вершин? Кажется второе, но я не уверен...

[Xaositect]

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

Простите, но не совсем понял про непересекающиеся пути. То есть граф обязательно планарен? Или подразумевалось отсутствие у путей общих вершин? Кажется второе, но я не уверен...

Отсутствие общих вершин.

[st256]

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

Ну и куда бы вы меня послали?

Сейчас уже никуда. http://www.telesys.ru практически не функционирует, на electronix.ru - одни ламеры (ну может пару-тройку отыскать приличных людей можно, но не более).

-- Пн сен 14, 2009 11:57:33 --

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

2st256Вот по совету Xaositect'а обращаюсь лично к вам. Вы получили оценку операций для вычисления той формулы из первого сообщения распределением сложности свертки (например операций) на все отсчеты? То есть ? Или не угадал? Заранее благодарю за ответ.

Я получил оценку 1 умножение на на один отсчет при любой длине свертки. Ну там еще может чуток добавиться, а может и нет. Смотря как организованы вычисления.

[ha]

Я что-то не понимаю. Как формула существенно зависящая от 2n независимых переменных может быть вычислена меньше чем за 2n-1 действие (вот меньше n умножений сделать можно.)? Обойтись одним умножением на одно скалярное произведение тоже очевидно нельзя (при достаточно больших n). Обойтись n умножениями для вычисления циклической свертки в n точках очевидно можно через БПФ (в случае целых чисел там можно обойтись сдвигами вместо умножений на $\varepsilon^n$).

[st256]

ha в сообщении #243846 писал(а):

Как формула существенно зависящая от 2n независимых переменных может быть вычислена меньше чем за 2n-1 действие

Не передергивайте. Ни про какие "действия" речи не велось. Говорили ТОЛЬКО об умножениях.

[ddn]

Xaositect писал(а):

Именно Колмогоров поставил задачу: доказать или опровергнуть гипотезу: нельзя произвести умножение двух $n$-значных чисел быстрее, чем за $n^2$.
Ученик Колмогорова Карацуба доказал, что она не верна и построил алгоритм, перемножающий их за $O(n^{\log_2 7})$. Тоом, будучи школьником, обобщил метод Карацубы и улучшил оценку до $O(n^{1+\varepsilon})$.
Немцы Шёнхаге и Штрассен применили к этой задаче преобразование Фурье и получили оценку $O(n\log n\log \log n)$.

С этими достижениями я познакомился по книжке "МЕЖДУНАРОДНЫЙ КОНГРЕСС МАТЕМАТИКОВ В БЕРКЛИ, 1986", а позже - Кнута, и только у него нашел детальное изложение алгоритма целочисленного дискретного ПФ (больше не найти никаких публикаций в интернете и библиотеках).
В первой же книжке упоминаются указанные Вами суперконцентраторы и их связь с нижней оценкой сложности для ЦДПФ (и умножения?), но больше нигде ничего про них не нашел, как и о работах Лесли Вальянта, открывшего линейные суперконцентраторы. Может Вам известно нечто большее по ним, чем содержится в этой книжке?

Плохо, что, опять же, дается только порядок роста сложности без указания величины множителя (для конкретной реализации, например схемами И, ИЛИ, НЕ над двоичными числами).

Еще бы интересно узнать точное значение сложности, найденные простым перебором, для конкретных небольших значений $n$ (перемножение двоичных чисел длины $n$ и $m$, при $n+m$ порядка десятка и меньше). Конечно, асимптотику $O(n\log n\log \log n)$ по этим значениям не увидеть - для этого нужны точные значение сложности для $n$ порядка сотен.

Xaositect писал(а):

А в позапрошлом году их алгоритм улучшил Фюрер, получив верхнюю оценку $O(n\log n 2^{O(\log^* n)})$.

Где можно узнать подробнее про результат Фюрера?
И поясните смысл выражения $2^{O(\log^* n)}$, нелепица получается.

[maxal]

Дискетное преобразование Фурье в применении к умножению чисел довольно подробно излагается Главе V книги "Алгебраическая алгоритмика":

Глава V. Дискретное преобразование Фурье 
1 Сложность умножения двух многочленов   
  1.1 Интерполяция многочленов над полем и над кольцом   
  1.2 Вычисление значений многочленов в корнях из единицы   
  1.3 Примитивные корни из единицы   
  1.4 Дискретное преобразование Фурье и циклическая свёртка   
  1.5 Обзор различных понятий   
2 Быстрое преобразование Фурье   
  2.1 Случай, когда порядок есть степень двойки   
  2.2 Случай, когда порядок — произвольная степень
  2.3 Пример итеративного алгоритма   
    2.3.1 От рекурсии к итерации   
    2.3.2 Суммы Йейтса   
3 Точное вычисление FFT: произведение многочленов   
  3.1 Реализация FFT, когда число точек есть степень 2   
  3.2 Как реализовать FFT?   
  3.3 Умножение многочленов   
  3.4 Реализация произведения многочленов   
  3.5 Вычисление преобразования Фурье   
4 Подробное рассмотрение метода Кули и Тьюки   
  4.1 Метод Кули-Тьюки для произведения двух множителей   
  4.2 Итерация метода Кули-Тьюки   
    4.2.1 Сложность итерационного метода Кули-Тьюки   
    4.2.2 Формулы для итераций по методу Кули-Тьюки   
5 Метод Гуда   
  5.1 Исследование примера 15 = 3 х 5   
  5.2 Теорема Гуда   
6 Вычисление семейства билинейных форм   
  6.1 Некоторые напоминания, определения и основные свойства   
  6.2 Тензорный ранг произведения двух многочленов   
  6.3 Пример: циклическая свертка порядка 4   
  6.4 Семейство билинейных форм и трилинейные формы   
  6.5 Пример: циклическая свёртка порядка 4 (продолжение)
7 Малые схемы для дискретного преобразования Фурье   
  7.1 DFT порядка р и СС порядка р - 1 (метод Рейдера)   
  7.2 Комбинация схем Рейдера и Гуда   
    7.2.1 Подробное изучение DFT3   
    7.2.2 Снова DFT5   
8 От FFT к тензорному произведению   
Упражнения   
Решения упражнений

[Xaositect]

ddn в сообщении #244193 писал(а):

С этими достижениями я познакомился по книжке "МЕЖДУНАРОДНЫЙ КОНГРЕСС МАТЕМАТИКОВ В БЕРКЛИ, 1986", а позже - Кнута, и только у него нашел детальное изложение алгоритма целочисленного дискретного ПФ (больше не найти никаких публикаций в интернете и библиотеках).В первой же книжке упоминаются указанные Вами суперконцентраторы и их связь с нижней оценкой сложности для ЦДПФ (и умножения?), но больше нигде ничего про них не нашел, как и о работах Лесли Вальянта, открывшего линейные суперконцентраторы. Может Вам известно нечто большее по ним, чем содержится в этой книжке?

Я ы этом треде уже советовал книгу "Alebraic Complexity Theory", там есть конструкция линейного суперконцентратора. Там и про умножение много, но в основном изложение теоретическое, скажем, алгоритм Ш-Ш излагается в применении к широкому классу колец, а не только к $\mathbb{Z}$.

ddn в сообщении #244193 писал(а):

Где можно узнать подробнее про результат Фюрера?И поясните смысл выражения , нелепица получается.

Статья Фюрера лежит в открытом доступе. http://www.cse.psu.edu/~furer/Papers/mult.pdf
Оценка, полученная в статье выглядит так: $T(n) \leq n \log n (2 ^{d \log^{*}{\sqrt[4]n}}-d')$ для некоторых констант $d$ и $d'$. Кратко ее пишут так: $n\log n 2^{O(\log^{*} n)}$, в том посте у меня внешнее О лишнее.
Есть еще позже опубликованный алгоритм, основанный не на комплексной, а на модулярной арифметике, с той же асимптотикой, константы, как пишет Фюрер в обновленной статье, чуть лучше. http://arxiv.org/pdf/0801.1416

[ddn]

Xaositect писал(а):

Оценка, полученная в статье выглядит так: $T(n) \leq n \log n (2 ^{d \log^{*}{\sqrt[4]n}}-d')$ для некоторых констант $d$ и $d'$. Кратко ее пишут так: $n\log n 2^{O(\log^{*} n)}$

Я не об этом. Просто $2^{O(\log^{*} n)}$ означает $n^{O(1)}=n^c$, что дает $n^{1+c}\log n$ - какое же это улучшение!? Если конечно не вкладывать особый смысл в $\log^{*}$ (логарифм со звездочкой). Я не понимаю.

Xaositect писал(а):

Я в этом треде уже советовал книгу "Alebraic Complexity Theory"

И ее можно скачать в интернете?

maxal писал(а):

Дискетное преобразование Фурье в применении к умножению чисел довольно подробно излагается Главе V книги "Алгебраическая алгоритмика"

Ее тоже можно найти и скачать?

Какие известны реализации минимальной сложности по малым значениям $n$?

[maxal]

ddn
Первая есть в электронном виде - http://www.poiskknig.ru/ вам в помощь.
Второй вроде бы нет.

[Xaositect]

ddn в сообщении #244213 писал(а):

Если конечно не вкладывать особый смысл в $\log^{*} n$ (логарифм со звездочкой). Я не понимаю.

Логарифм со звездочкой - это минимальное число раз, которое надо взять логарифм от n, чтобы получить число, меньшее 1. http://en.wikipedia.org/wiki/Iterated_logarithm

[maxal]

Впрочем, вот есть раздел "4. Подробное рассмотрение метода Кули и Тьюки":
http://ifolder.ru/10514530