7.6. Определение пилообразного преобразования
Рассмотренные выше пилообразные матрицы можно использовать для определения пилообразного преобразования, которое записывается как
(7.6.1)
где 
- вектор коэффициентов пилообразного преобразования; 
— вектор входной последовательности, 
— пилообразная матрица размером 
.
Базисными векторами пилообразного преобразования являются строки пилообразной матрицы 
. На рис. 7.5 приведены базисные векторы пилообразного преобразования для 
и базисные векторы ПУА, упорядоченным по Уолшу. Как видно из этого рисунка, строки с индексами с 9 по 12 совпадают.
Рис. 7.5. Сравнение базисных векторов ПУА с упорядочением по Уолшу и пилообразного преобразования при 
.
Быстрый алгоритм вычисления пилообразного преобразования. Пилообразное преобразование можно осуществить с помощью быстрого алгоритма, который наиболее просто продемонстрировать для 
. При этом выражение (7.6.1) записывается в виде
(7.6.2)
где 
определяется из выражения (7.5.6). Наличие быстрого алгоритма становится очевидным при факторизации матрицы преобразования на произведение разреженных матриц:
(7.6.3)
С помощью приведенной выше факторизации пилообразное преобразование можно вычислить, как показано на рис. 7.6. Из рассмотрения графа преобразования можно сделать вывод, что для получения коэффициентов пилообразного преобразования 
, необходимо выполнить восемь сложений/вычитаний и шесть умножений.
Рис. 7.6. Граф пилообразного преобразования, 
