Текст подпрограммы и версий ( Фортран )
amc1r.zip , amc1c.zip 		Тексты тестовых примеров ( Фортран )
tamc1r.zip , tamc1c.zip
Текст подпрограммы и версий ( Си )
amc1r_c.zip , amc1c_c.zip 		Тексты тестовых примеров ( Си )
tamc1r_c.zip , tamc1c_c.zip
Текст подпрограммы и версий ( Паскаль )
amc1r_p.zip , amc1c_p.zip 		Тексты тестовых примеров ( Паскаль )
tamc1r_p.zip , tamc1c_p.zip

Подпрограмма:  AMC1R

Назначение

Вычисление произведения вещественной циркулянтной матрицы на вещественный вектор или произведения двух вещественных циркулянтных матриц на основе алгоритма Быстрого Преобразования Фурье. Подпрограмма может использоваться также для вычисления вещественных периодических сверток.

Математическое описание

Задана циркулянтная матрица А размерности N*N: 

                   |  a0     aN-1  aN-2   ...   a2  a1    |
                   |  a1     a0     aN-1   ...   a3  a2    |
                   |  a2     a1      a0     ...   a4   a3    |
(1)    A   =   |  . . . . . . . . . . . . . . . . . . . . . . .            ,
                   |  aN-2  aN-3  aN-4   ...  a0  aN-1  |
                   |  aN-1  aN-2  aN-3   ...  a1   a0    |

которая определяется N элементами первого столбца  a0, a1, ..., aN-1, переставляемыми циклически. Требуется вычислить вектор  y = Ax = (y0, y1,..., yN - 1), где вектор  x = (x0, x1,..., xN - 1) также задан. Эта задача сводится к вычислению периодической (круговой) свертки двух последовательностей  as,  xs,  s = 0, 1, ..., N - 1 одинаковой длины N [1], т.е. 

                            N-1 
            ys      =      ∑     as -j x j ,       s = 0, 1, ... , N-1 ,
                             j=0

где ряд as продолжен периодически с периодом N для отрицательных значений индекса  s:  a - s = aN - s ,  s = 1, 2, ..., N - 1.

Пусть F - оператор Дискретного Преобразования Фурье, задаваемый формулой (например, для ряда  as): 

                          N-1
Bm  =  F(as)  =    ∑     as exp (-2 p i m s / N) ,     m = 0, 1,..., N-1 ,   i = (-1)1/2;
                           s=0

аналогично Vm = F(xs), Wm = F(ys),  s = 0, 1, ..., N - 1. На основании теоремы о дискретной круговой свертке [1] 

            Wm = Bm* Vm ,    m = 0, 1, ..., N-1 .

Искомый вектор y находится с помощью Обратного Дискретного Преобразования Фурье F -1 от произведения ДПФ рядов  as и  xs : 

  ys  =  F -1(Wm)  =
                                         N-1
                          =  1/N      ∑    Bm* Vm exp (2 p i m s / N) ,    s = 0, 1,..., N-1,
                                         m=0

Для эффективного вычисления ДПФ и ОДПФ применяется быстрое преобразование Фурье [2], за счет которого число операций в pеализованном алгоритме пропорционально N log2 N и требуется память длины 2N.

Описанный метод можно также применять для быстрого умножения двух циркулянтных матриц: А и матрицы C вида (1), определяемой вектором  x = (x0, x1,..., xN - 1), при этом вектор  y = Ax = (y0, y1,..., yN - 1), определяет циркулянтную матрицу вида (1) произведения A C.

1.  Б.Голд, Ч.Pейдер. Цифровая обработка сигналов. М.,"Советское радио", 1973.
2.  В.А.Морозов, Н.Н.Кирсанова, А.Ф.Сысоев. Комплекс алгоритмов быстрого преобразования Фурье дискретных рядов, Сб. "Численный анализ на ФОPТPАНе", вып.15, Изд - во МГУ, М., 1976.

Использование 

    SUBROUTINE  AMC1R (N, B, X) 
   Параметры
N - размерность исходной матрицы А, равная целой степени числа два, N ≥ 4 (тип: целый);
B - вещественный одномерный массив длины N, содержащий заданные определяющие элементы матрицы А:  a0,  a1, ..., aN - 1,
X - вещественный одномерный массив длины N, содержащий заданные компоненты вектора x = (x0, x1,..., xN - 1) на входе и вычисленные компоненты вектора  y = (y0, y1,..., yN - 1) на выходе. 
   Версии
AMC1C - вычисление произведения комплексной циркулянтной матрицы А на комплексный вектор X или произведения двух комплексных циркулянтных матриц. Для подпрограммы АMC1C параметры B, X имеют тип СОМРLЕХ. 
   Вызываемые подпрограммы
 FTF1C -
 FTF2C   		подпрограммы вычисления Дискретного или Обратного Дискретного Преобразования Фурье комплексного ряда длины, равной степени двух, методом быстрого преобразования Фурье (отличаются друг от друга способом представления исходного ряда); используются в АМС1R и АMC1C соответственно. 
   Замечания по использованию
  1. 

После выхода из подпрограммы АМС1R и АMC1C значения определяющих элементов исходной матрицы А в массиве B не сохраняются.

  2. 

Если циркулянтная матрица А имеет вид 

              | a0        a1        a2  ...  aN-1   |
              | aN-1     a0        a1  ...  aN-2   |
              | aN-2     aN-1     a0  ...  aN-3   |
              | . . . . . . . . . . . . . . . . . . . . .
              | a1         a2        a3  ...  a0      |

и задается N элементами первой строки  a0,  a1, ..., aN - 1, то до обращения к подпрограммам АМС1R и АMC1C эти элементы нужно упорядочить в массиве B следующим образом:  a0, aN - 1, aN - 2, ..., a1.

Примеры использования 

   1.
      DIMENSION  B(8), X(8)
      DATA  B /1., 8., 7., 6., 5., 4., 3., 2./
      DATA  X /1., -1., -2., 3., 0., 2., -3., 0./
      N = 8
      CALL  AMC1R (N, B, X)

Результат:    y  =  (-4., 4., -4., -20., 4., 4., 20., -4.)

   2.
      COMPLEX  B(4), X(4)
      DATA  B /(1., 1.), (4., -1.), (3., 2.), (2., 0.)/
      DATA  X /(1., -1.), (-1., 0.), (-2., 1.), (3., -2.)/
      N = 4
      CALL  AMC1C (N, B, X)
 
Результат:  y  =  ( (2., -12.), (11., -4.), (4., -5.), (-3., 3.) )