Необходимо аппроксимировать 400 точек полиномом 11 степени, потом полиномы 11 степени будут передаваться по медленному каналу связи...
Есть ли какие-нибудь готовые алгоритмы для этого?..

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

Полином 11-ой степени уже не подарок, т.к. расчет в лоб потребует инвертирования матрицы, которая к тому же очень плохо определена (близка к матрице Гильберта). Поэтому такой расчет на AVR лучше не делать, а если и посылать в него данные, то не коэффициенты полинома, а уже готовую обращенную матрицу, чтобы тот только множил на нее вектор данных и больше ни о чем не заботился. А ту матрицу пусть хоть писюк посчитает. Только при этом нужно учесть, что такая матрица-сомножитель для вашего случая будет иметь размерность 400x11=4400 элементов, а если каждый по 4 байта (тип float), то выйдет 17.6 килобайт. Уже многонько, не каждая AVR-ка потянет. А с точностью double потребуется еще вдвое больше памяти. Да и само умножение получится не быстрым при такой большой матрице и медленной реализации умножения.

А если говорить об алгоритмах, то тут, полагаю, надо попытать расчет коэффициентов через полиномы Чебышева. Кажется где-то есть такой способ, отличающийся устойчивостью. Однако в любом случае AVR придется делать одну и ту же операцию умножения вектора длиной 400 на матрицу размером 400х12. А алгоритмы будут различаться между собой только тем, как такая матрица вычисляется. В любом случае вычислять ее надо будет не на AVR, а засылать ему уже готовую.

Какое время выделяется на обсчет?

0.7 секунды

Аппроксимировать полиномом 11-й степени?
Вы уверены, что это действительно хорошая идея?

А Вы для начала алгоритм в том-же матлабе или просто на С/С++ уже промоделировали?
Всё устойчиво и хорошо опраксимирует? Что-то подсказывает что будут проблемы с точностью опраксимации,
уж очень много точек на один полином. Если только у точек не какой хитрый закон, которых хорошо ляжет на
полином.
Если у Вас на руках есть алгоритм, как делали? Неужели там нет много матриччных вычислений?
Давно что-то похожее делал, подробности забыл, но для нахождения параметров полинома использовались множители Лагранжа.
Так помнится были проблемы, часто после апроксимации, при проверке качества апроксимации результат был плохой.
Хотя у меня было много граничных условий, в Вашем случае может всё лучше будет работать.
После чего участо разбивался на 2 части, и для них всё считалось одельно. И так дробил отрезок, покуда не получал нужной точности апроксимации.
Возможно этот алгоритм не очень хорошо работал, но тем не менее, есть сомнненя что 400 точек лягут на один полином.

Ну а по теме, 0,7 секунды на AVR для 400 точек, IMHO не реально, у вас будут большие матрыцы, не позубам так быстро считать для AVR.

+1 Не успеет

Вообще-то за 0.7 сек можно спокойно передать эти 400 точек даже по самому медленному из существующих каналов. И не мучить АВРку.

Я уверена в обратном.

В мобильнике считается полином 10 степени и от ~ 270 точек, квантованных на 8000 Гц.
На обсчет полинома тратится где-то 1% времени 16-битного микропроцессора с производительностью 20MIPS.
Так что AVR, если будет только полином считать, то может и успеет.

Ну еще полином 255-й степени в общеупотребимых кодах Рида-Соломона вспомни.

http://www.google.ru/search?&q=polynomial+fitting

только почему она нелинейная-то?


Ну матрица будет всего 11х11, не так уж и много. Если даже по Гауссу занулять, за секунду вроде можно успеть, да и операции с плавающей запятой наверное можно ускорить немного, от точности зависит, никто же соответствия ieee-754 не требует.

Однако, целесообразность сего действа действительно крайне сомнительна.

Но только еще эту матрицу надо заполнить суммами. Плюс отдельный вопрос про вычислительную устойчивость алгоритма. В общем случае если использовать метод "в лоб" при 32 битных float может терять устойчивость при степенях полинома >6

По поводу вычислительной устойчивости на самом деле вопросов нет. Число обусловленности для матрицы составленной из векторов полиноминального базиса до 10 порядка для интервала 0-1 составляет порядка 22 миллионов. В такой ситуации о вычислительной устойчивости алгоритма говорить не приходится.

Это была оценка вычислительной сложности.Конкретнее следующее.
Если взять какой-нибудь стандарт компрессии речи типа G721, то там есть Си-программки,
в том числе и нахождение АР-модели кадра речи - ее можно взять за основу и даже странслировать в AVR.
Правда, степень полинома нужно будет увеличить с10 до 11.
В стандарте программа сделана очень профессионально -есть чему поучиться.