0.1 Preliminaries

Automatic generation of prime Page 5 / 5

R_{9} \otimes R_{5} = (R_{9} \otimes I_{5}) (I_{9} \otimes R_{5})

and

R_{9} \otimes R_{25} \otimes R_{7} = (R_{9} \otimes I_{175}) (I_{9} \otimes R_{25} \otimes I_{7}) (I_{225} \otimes R_{7})

When this factored form of $\otimes R_{n_{i}}$ or any of the variations alluded to above, is used, the number of additions incurred is given by

\begin{matrix} \sum_{i = 1}^{k} \frac{N}{p_{i}^{e_{i}}} A (R_{p_{i}^{e_{i}}}) & = & \sum_{i = 1}^{k} \frac{N}{p_{i}^{e_{i}}} 2 (p_{i}^{e_{i}} - 1) \\ = & 2 N \sum_{i = 1}^{k} 1 - \frac{1}{p_{i}^{e_{i}}} \\ = & 2 N (k - \sum_{i = 1}^{k} \frac{1}{p_{i}^{e_{i}}}) \end{matrix}

where $N = p_{1}^{e_{1}} \dots p_{k}^{e_{k}}$ .

Although the use of operations of the form $R_{p_{1}^{e_{1}}} \otimes \dots \otimes R_{p_{k}^{e_{k}}}$ is simple, it does not exactly separate the circular convolution into smaller disjoint convolutions.In other words, its use does not give rise in [link] and [link] to block diagonal matrices whose diagonalblocks are the form $\otimes_{i} C_{Φ_{p_{i}}}$ . However, by reorganizing the arrangement of theoperations we can obtain the block diagonal form we seek.

First, suppose $A$ , $B$ and $C$ are matrices of sizes $a \times a$ , $b \times b$ and $c \times c$ respectively. If

T B T^{- 1} = [\begin{matrix} B_{1} \\ B_{2} \end{matrix}]

where $B_{1}$ and $B_{2}$ are matrices of sizes $b_{1} \times b_{1}$ and $b_{2} \times b_{2}$ , then

Q (A \otimes B \otimes C) Q^{- 1} = [\begin{matrix} A \otimes B_{1} \otimes C \\ A \otimes B_{2} \otimes C \end{matrix}]

where

Q = [\begin{matrix} I_{a} \otimes T (1 : b_{1}, :) \otimes I_{c} \\ I_{a} \otimes T (b_{1} + 1 : b, :) \otimes I_{c} \end{matrix}] .

Here $T (1 : b_{1}, :)$ denotes the first $b_{1}$ rows and all the columns of $T$ and similarly for $T (b_{1} + 1 : b, :)$ . Note that

[\begin{matrix} A \otimes B_{1} \otimes C \\ A \otimes B_{2} \otimes C \end{matrix}] \neq A \otimes [\begin{matrix} B_{1} \\ B_{2} \end{matrix}] \otimes C .

That these two expressions are not equal explains why the arrangement of operations must be reorganizedin order to obtain the desired block diagonal form. The appropriate reorganization is described by theexpression in [link] . Therefore, we must modify the transformation of [link] appropriately. It should be noted that this reorganization ofoperations does not change their computational cost. It is still given by [link] .

For example, we can use this observation and the expression in [link] to arrive at the following similarity transformation:

Q (S_{p_{1}} \otimes S_{p_{2}}) Q^{- 1} = [\begin{matrix} 1 \\ C_{Φ_{p_{1}}} \\ C_{Φ_{p_{2}}} \\ C_{Φ_{p_{1}}} \otimes C_{Φ_{p_{2}}} \end{matrix}]

where

Q = [\begin{matrix} I_{p_{1}} \otimes 1_{{-p}_{2}}^{t} \\ I_{p_{1}} \otimes G_{p_{2}} \end{matrix}] (R_{p_{1}} \otimes I_{p_{2}})

$1_{-p}$ is a column vector of $p$ 1's

1_{-p} = {[\begin{matrix} 1 & 1 & \dots & 1 \end{matrix}]}^{t}

and $G_{p}$ is the $(p - 1) \times p$ matrix:

G_{p} = [\begin{matrix} 1 & - 1 \\ 1 & - 1 \\ ⋱ & ⋮ \\ 1 & - 1 \end{matrix}] = [\begin{matrix} I_{p - 1} - {\underset{̲}{1}}_{p - 1} \end{matrix}] .

In general we have

R (S_{p_{1}^{e_{1}}} \otimes \dots \otimes S_{p_{k}^{e_{k}}}) R^{- 1} = \underset{d | n}{\oplus} Ψ (d)

where $R = R_{p_{1}^{e_{1}}, \dots, p_{k}^{e_{k}}}$ is given by

R_{p_{1}^{e_{1}}, \dots, p_{k}^{e_{k}}} = \prod_{i = k}^{1} Q (m_{i}, p_{i}^{e_{i}}, n_{i})

with $m_{i} = \prod_{j = 1}^{i - 1} p_{j}^{e_{j}}$ , $n_{i} = \prod_{j = i + 1}^{k} p_{j}^{e_{j}}$ and

Q (a, p^{e}, c) = \prod_{j = 0}^{e - 1} [\begin{matrix} I_{a} \otimes 1_{- p}^{t} \otimes I_{c p^{j}} \\ I_{a} \otimes G_{p} \otimes I_{c p^{j}} \\ I_{a c (p^{e} - p^{j + 1})} \end{matrix}] .

$1_{-p}$ and $G_{p}$ are as given in [link] and [link] .

R (S_{9} \otimes S_{5}) R^{- 1} = [\begin{matrix} 1 \\ C_{Φ_{3}} \\ C_{Φ_{9}} \\ C_{Φ_{5}} \\ C_{Φ_{3}} \otimes C_{Φ_{5}} \\ C_{Φ_{9}} \otimes C_{Φ_{5}} \end{matrix}]

where

\begin{matrix} R & = & R_{9, 5} \\ = & Q (9, 5, 1) Q (1, 9, 5) \end{matrix}

and

R

can be implemented with 152 additions.

Notice the distinction between this example and example "Reduction Operations" . In example "Reduction Operations" we obtained from $S_{9} \otimes S_{5}$ a Kronecker product of two block diagonal matrices, but here we obtaineda block diagonal matrix whose diagonal blocks are the Kronecker product of cyclotomic companionmatrices. Each block in [link] represents a multi-dimensional cyclotomic convolution.

A Matlab program that carries out the operation $R_{p_{1}^{e_{1}}, \dots, p_{k}^{e_{k}}}$ in [link] is KRED() .

function x = KRED(P,E,K,x)
% x = KRED(P,E,K,x);% P : P = [P(1),...,P(K)];% E : E = [E(K),...,E(K)];for i = 1:K
   a = prod(P(1:i-1).^E(1:i-1));c = prod(P(i+1:K).^E(i+1:K));
   p = P(i);e = E(i);
   for j = e-1:-1:0x(1:a*c*(p^(j+1))) = RED(p,a,c*(p^j),x(1:a*c*(p^(j+1))));
   endend

It calls the Matlab program RED() .

function y = RED(p,a,c,x)
% y = RED(p,a,c,x);y = zeros(a*c*p,1);
for i = 0:c:(a-1)*cfor j = 0:c-1
      y(i+j+1) = x(i*p+j+1);for k = 0:c:c*(p-2)
         y(i+j+1) = y(i+j+1) + x(i*p+j+k+c+1);y(i*(p-1)+j+k+a*c+1) = x(i*p+j+k+1) - x(i*p+j+c*(p-1)+1);
      endend
end

These two Matlab programs are not written to run as fast as they could be.They are a `naive' coding of $R_{p_{1}^{e_{1}}, \dots, p_{k}^{e_{k}}}$ and are meant to serve as a basis for more efficient programs. In particular, the indexing and the loop counters canbe modified to improve the efficiency. However, the modifications that minimize the overheadincurred by indexing operations depends on the programming language, the compiler and the computer used.These two programs are written with simple loop counters and complicated indexing operationsso that appropriate modifications can be easily made.

Inverses

The inverse of $R_{p}$ has the form

R_{p}^{- 1} = \frac{1}{p} [\begin{matrix} 1 & p - 1 & - 1 & - 1 & - 1 \\ 1 & - 1 & p - 1 & - 1 & - 1 \\ 1 & - 1 & - 1 & p - 1 & - 1 \\ 1 & - 1 & - 1 & - 1 & p - 1 \\ 1 & - 1 & - 1 & - 1 & - 1 \end{matrix}]

and

R_{p^{e}}^{- 1} = \prod_{k = 0}^{e - 1} ((R_{p}^{- 1} \otimes I_{p^{e - 1 - k}}) \oplus I_{p^{e} - p^{e - k}}) .

Because the inverse of $Q$ in [link] is given by

Q^{- 1} = [\begin{matrix} I_{a} \otimes T^{- 1} (:, 1 : b_{1}) \otimes I_{c} & I_{a} \otimes T^{- 1} (:, b_{1} + 1 : b) \otimes I_{c} \end{matrix}]

the inverse of the matrix $R$ described by eqs [link] , [link] and [link] is given by

R^{- 1} = \prod_{i = 1}^{k} Q {(m_{i}, p_{i}^{e_{i}}, n_{i})}^{- 1}

with $m_{i} = \prod_{j = 1}^{i - 1} p_{j}^{e_{j}}$ , $n_{i} = \prod_{j = i + 1}^{k} p_{j}^{e_{j}}$ and

Q {(a, p^{e}, c)}^{- 1} = \prod_{j = e - 1}^{0} [\begin{matrix} I_{a} \otimes 1_{-p}^{t} \otimes I_{c p^{j}} & I_{a} \otimes V_{p} \otimes I_{c p^{j}} \\ I_{a c (p^{e} - p^{j + 1})} \end{matrix}]

where $V_{p}$ denotes the matrix in [link] without the first column. A Matlab program for $R^{t}$ is tKRED() , it calls the Matlab program tRED() . A Matlab program for $R^{- t}$ is itKRED() , it calls the Matlab program itRED() . These programs all appear in one of the appendices.

<< Chapter < Page Page > Chapter >>

Read also:

Get Jobilize Job Search Mobile App in your pocket Now!

100% Free Mobile Applications
Receive real-time job alerts and never miss the right job again

Source: OpenStax, Automatic generation of prime length fft programs. OpenStax CNX. Sep 09, 2009 Download for free at http://cnx.org/content/col10596/1.4

Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Automatic generation of prime length fft programs' conversation and receive update notifications?

Ask

©flickr: Alexander	Mechanics I MCQ By Stephanie Redfern Start Quiz
	9 Sociology 09 Social Stratification in the US MCQ By OpenStax Start Quiz
	My OCA Mock By Mike Wolf Start Exam
	6 BOD Respiratory Exam By Brooke Delaney Start Exam
©flickr:	Microbiology Final By Szilárd Jankó Start Quiz
	Assembly Programming Language By JavaChamp Team Start Quiz
	4 Microbiology Final 4 By Madison Christian Start Quiz
	1 Neuroanatomy 01 The Cranial Nerves By Stephen Voron Start Quiz
©flickr:	The Minute Man Hose Load By Michael Pitt Start Quiz
	1 Microeconomics 01 What Is Economics? By OpenStax Start Flashcards