Новый алгоритм MIT в десятки раз ускоряет быстрое преобразование Фурье



    На симпозиуме по дискретным алгоритмам ACM на этой неделе группа исследователей из MIT представила новый алгоритм быстрого преобразования Фурье sFFT (Sparse Fast Fourier Transform), который на некоторых задачах может быть в десятки или сотни раз быстрее классического БПФ.

    Преобразование Фурье предполагает получение коэффициентов («амплитуд») при разложении исходной функции на элементарные составляющие — гармонические колебания с разными частотами. Быстрое преобразование Фурье позволяет ускорить этот процесс за счёт разделения вектора коэффициентов на два вектора, рекурсивном вычислении ДПФ для них, и объединении результатов в одно БПФ. Считается, что метод БПФ предложен в 1805 году Гауссом и переоткрыт в 1965 году, после чего нашёл широкое применение с распространением современных компьютеров. В последние 50 лет предпринималось немало попыток повысить эффективность БПФ, например, FFTW.

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

    Алгоритм sFFT (Sparse Fast Fourier Transform) создан на основе двух существующих фильтров (фильтр Гаусса и фильтр Чебышева) и нацелен на то, чтобы быстро найти фрагменты с «разреженным» сигналом (sparse signal) и определить исходную амплитуду в каждом из них. Сигнал разбивается на фрагменты (rapid sampling) до тех пор, пока не останется разреженный сигнал с единственной амплитудой. А уже там новый алгоритм выявляет её в 10 тыс. раз быстрее классического БПФ.

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

    via MIT
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 34
    • НЛО прилетело и опубликовало эту надпись здесь
      • +13
        Не у одного. Но предыдущий пост, похоже, удалён.
        • +20
          Как и в прошлой версии — затронута важная тема, но о сути ни слова, одна желтуха.
          • +20
            Этот автор по-другому не пишет.
            • –1
              По ссылке все есть.
          • +7
            Следующая редакция будет еще короче?)
            • +31
              MIT… а я вот сижу, пишу раздел «Охрана труда» для диплома, 20 страниц не имеющих к ниму вообще отношения… плюс потом еще «Гражданская оборона»… А они вот написали свой алгоритм, и даже не подозревают какому страшному воздействию ЭЛТ-трубок от ЭВМ подверглись, и какой план эвакуации при пожаре…
              • +1
                Имхо, во всём MIT не найти ниодной ЭЛТ-трубки уже. И у нас есть такие вузы.
                • +4
                  Не только в МТИ в дипломах не требуют писать эту билеберду. Вы, вероятно, в каком-то инженерно-техническом институте учитесь? А вот в университетах не.
                  • +3
                    В МГТУ им. Баумана требуются эти разделы, хотя это и университет.
                    • +7
                      Но положа руку на сердце они не пишутся, а копипастятся из дипломов прошлых лет с заменой цифр :)
                      • +2
                        Странно, у нас за 6 лет не требовали. Может еще от кафедры и предмета зависит.
                        • +2
                          На некоторых кафедрах ИУ еще и гос экзамен остался)
                          • +1
                            Гм. Именно технический институт. Как и все остальные нижеперечисленные. Там даже во всех наиметованиях специальная буковка Т включена. То, что сейчас МГТИ им Баумана переименовали в МГТУ — это не более, чем постперестроечный технический трюк ради каких-то дополнительных плюшек финансирования.
                          • +1
                            В Российских инженерно-технических, как и в университетах, все Научно исследовательские работы оформляются по ГОСТ 7.32-2001. А в нем таких подозрительных разделов не имеется…
                            • +1
                              Курсовые работы, проекты, дипломы не являются научно исследовательскими работами. Даже у магистров, обучение которых обязательно имеет исследовательский уклон. По этому, если подходить к вопросу строго по ГОСТу, то государственных стандартов на оформление такого рода работ нет.

                              При этом вузовский стандарт для учебных работ может базироваться на ГОСТ 7.32-2001. Например, у нас на факультете требуют оформлять учебные работы в соответствии с вышеназванным ГОСТ. Возможно требование использовать стандарты ЕСКД или ЕСПД, но это опять же требования вузов, а не государства.

                              Если рассматривать структуру дипломных проектов, то она зависит от направления подготовки и присваиваемой квалификации (дипломные работы бакалавров, магистров и инженеров отличаются по своей структуре достаточно сильно). В дипломных работах инженеров разделы БЖ и экономическая часть, насколько мне известно, обязательны. У бакалавров и магистров этих разделов, насколько я знаю, нет. К сожалению, проконсультироваться на счет наличия требования к содержанию дипломов в ГОСах я сейчас не могу, поэтому приходится надеяться, что моя память меня не подводит.

                              Более того, я бы еще ужесточил требования к содержанию этих разделов, обязательно привязав их содержание к разрабатываемой в рамках диплома системе, а то когда видишь инженеров-пятикурсников, которые искренне не понимают зачем нужно учитывать стоимость сопровождения ПО при оценке разного рода затрат и которые пишут допустимый диапазон температур для офисного работника от +10 до +30 градусов при 8-и часовом рабочем дне, то волосы дыбом встают! Это я в декабре присутствовал на защитах курсовых проектов, которые у пятикурсников нашей кафедры должны перетекать в дипломные проекты.
                            • +3
                              МИРЭА(теперь тоже МГТУ, как и бауманка) — раздел о безопасности жизнедеятельности обязателен.
                              • +2
                                Новосибирский ГТУ, факультет прикладной математики и нформатики. Раздел БЖД обязателен.
                                • +2
                                  Алтайский ГТУ, факультет информационных технологий, по СТО (стандарт организации) обязательны разделы БЖД и экономики.
                              • +39
                                В век говнокодерства и пустой траты ресурсов, успехи математиков вселяют веру в светлое будущее.
                                • –1
                                  Никакой магии, это же не настоящее преобразование Фурье, а аппроксимация суммой нескольких синусоид. Ну да, быстро ;)
                                  • +6
                                    Хотелось бы уточнить, что любое дискретное преобразование Фурье (в частности быстрое) — суть разложение дискретной функции на сумму конечного числа синусоид (точнее, правда, e±i…). По ссылке сказано, что функция работает за время O(k log k) для сигнала, в ДПФ которого не более k ненулевых коеффициентов и за время O(k log k log(n/k)) для произвольного сигнала. Т.е. вроде как оптимальнее БПФ. Но естественно информации маловато (что там за коэффициент — никто не знает, может он начинает выигрывать у БПФ только при n > 106).
                                    • +1
                                      Там определенные условия для того, чтобы оно сильно ускоряло. O(*) — это ассимптотическая оценка сверху, соответственно, в худшем случае этот алгоритм не сильно лучше
                                      • +1
                                        Оценка сверху это и есть оценка «в худшем случае».
                                        • +1
                                          А я я что сказал?
                                          • +1
                                            Просто непонял как-то было к чему это в ответ на мой коментарий и неверно понял, наверное.

                                            В самом описании алгоритма много неясного. Например, какие ограничения на k? Если k взять равным 1, то получается O(log2n). Наверное какие-то ограничения должны быть. В общем, пока не увидим алгоритм — неясно что это и с чем его едят.
                                            • +1
                                              Хотя надо ближе глянуть тот PDF, может там всё и расписано.
                                    • +3
                                      Любое ДФП суть аппроксимация ;) только теплые ламповые интегралы могут дать точное преобразование.
                                    • +6
                                      Господа, я не понимаю, в чем есть смысл искать компоненты с разряженными матрицами, если суть БПФ как раз в представлении матрицы в сумму разряженных. Это и так и так придется делать для всех элементов…
                                      Да и потом, есть же дискретное преобразование Хартли, открытое Брейнсуэлом еще в 1980 (основанное вместо sin(x) на cas(x), т.е. на sin(x)+cos(x), что полностью позволяет избавится от комплексной составляющей), на основе которого построено БПХ, и существует элементарная взаимосвязь с ДПФ. Уже не раз было доказано, что этот способ является наиболее быстрым. Так, простите, почему же не приведено сравнение с этим алгоритмом в их научной работе?
                                      • +11
                                        Спрашивать такие вопросы у Ализара, это как спорить с переводом.
                                        • +5
                                          БПХ считалось наиболее быстрым пока операции умножения были гораздо более затратными по сравнению с операциями сложения. Сейчас же когда 1 оп.ум. ~ 1 оп. сл. преимущества БПХ перед БПФ теряются.

                                          Вот что говорят разработчики FFTW о БПХ:
                                          «If you are planning to use the DHT because you've heard that it is “faster” than the DFT (FFT), stop here. The DHT is not faster than the DFT.»
                                          • +1
                                            Операция сложения эквивалентна операции умножения еще со времен разработки умножатора. Ну а что в этом нового?

                                            Фишка ведь в том, что для того, чтобы перемножить два числа, используя ДПХ, надо перемножить эти числа, а чтобы перемножить два числа в ДПФ, надо перемножить два комплексных числа, т.е.

                                            где надо потратить 4 операции умножения и 2 операции сложения.

                                            Аппаратного перемножения комплексных чисел еще не придумали, а жаль.
                                            • +3
                                              Вы ставите эффективность алгоритма в прямую зависимость от количества операций — на данный момент это теряет смысл т.к. эффективность многих алгоритмов зависит от того как процессор работает с кэшем и как у него организовано выполнение операций.
                                              В случае работы с действительными числами скорость БПФ и БПХ примерно одинакова и преимущество БПХ есть ни что иное как заблуждение.
                                              Я понимаю что мои слова могут быть неубедительными для вас, но вы можете самостоятельно почитать что пишут об этом разработчики FFTW — люди, которых можно считать более чем авторитетными в данной области.
                                              • 0
                                                Еще Тьюрингом была предложена система оценки эффективности алгоритмов с помощью двух измерений: емкостная трудоемкость, показывающая необходимое количество дополнительной памяти для выполнение алгоритма и временная трудоемкость, показывающая необходимое количество элементарных шагов для выполнения алгоритма.

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

                                                Если сравнивать аппаратную часть, то здесь всегда будет преобладать алгоритм на более «продвинутом» железе, но это сравнение сейчас не имеет никакого смысла, т.к. мы сравниваем два алгоритма, и более разумно их сравнить на одном железе и реализованные на одной платформе, если фас интересует именно производительная испытательная сложность, я же говорю о теоретических расчетах, без которых нельзя заключить об эффективности алгоритма, так же как о его единственности и правильности полученного с помощью него решения.

                                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.