# A Parallel Framework with Block Matrices of a Discrete Fourier Transform for Vector-Valued Discrete-Time Signals

Authors: Pablo Soto-Quiros
Journal: The Scientific World Journal
 (2015)

---

## Abstract

This paper presents a parallel implementation of a kind of discrete Fourier transform (DFT): the vector-valued DFT. The vector-valued DFT is a novel tool to analyze the spectra of vector-valued discrete-time signals. This parallel implementation is developed in terms of a mathematical framework with a set of block matrix operations. These block matrix operations contribute to analysis, design, and implementation of parallel algorithms in multicore processors. In this work, an implementation and experimental investigation of the mathematical framework are performed using MATLAB with the Parallel Computing Toolbox. We found that there is advantage to use multicore processors and a parallel computing environment to minimize the high execution time. Additionally, speedup increases when the number of logical processors and length of the signal increase.


---

## Body

## 1. Introduction

Letl2(Zn,Cd) be the space of vector-valued discrete-time signals with n samples, where each sample is a complex vector of length d. The vector-valued discrete-time signals are used very often in several applications in signal processing and electrical engineer, for example, vector quantization of images [1], time-frequency localization with wavelets [2], image coding [3], vector filter bank theory [4], linear time-dependent MISO [5], and analysis of MMSE estimation for compressive sensing of block sparse signals [6].Now, to analyze the spectra of vector-valued discrete-time signals, a novel tool was developed, and it is calledvector-valued DFT [7, 8]. This transform has applications in vector analysis in complex, quaternion, biquaternion, and Clifford algebras [8]. Additionally, the vector-valued DFT is used in digital signal processing, for example, the study of new complex valued constant amplitude zero autocorrelation (CAZAC) signals [9], which serve as coefficients for phase coded waveforms with prescribed vector-valued ambiguity function behavior, which is relevant in light of time-frequency analysis, vector sensor, and MIMO technologies [7].The following paper presents a parallel framework of the vector-valued DFT. The major contributions of this paper are summarized as follows:(1)
The construction of a new mathematical structure for the vector-valued DFT using block matrix theory such that it allows a parallel implementation in multicore processors.(2)
Reducing the elapsed time to compute the vector-valued DFT of a vector-valued discrete-time signal using parallel computing through aforementioned new mathematical framework.This new framework is developed with a set of block matrix operations, for example, Kronecker product, direct sum, stride permutation, vec operator, and vec inverse operator (see Section2.1 for details). These block matrix operations contribute to analysis, design, and implementation of parallel algorithms in multicore processors [10–12]. This mathematical framework is inspired in the matrix representation of the Cooley-Tukey fast Fourier transform (FFT) algorithm for complex discrete-time signals, corresponding to the decomposition of the transform size n into the product of two factors r and s, which is developed in [10, 12, 13].The present paper is organized as follows. Section2 explains a mathematical background about block matrix operations and discrete Fourier transform. Section 3 defines the concept of vector-valued DFT for vector-valued discrete-time signals. Section 4 develops a mathematical framework of vector-valued DFT in terms of block matrix operations for vector-valued discrete-time signals with length n=rs. This mathematical framework contributes to implementation of parallel algorithms. Section 5 explains an implementation and experimental investigation of this mathematical framework using parallel computing in multicore processors with MATLAB. Finally, some conclusions are presented in Section 6.Throughout the paper, the following notations are used.Zn={0,1,…,n-1} is the additive group Z of integers modulo n, Cm×n is the matrix space of m rows and n columns with complex numbers entries and Cn=Cn×1. The rows and columns of A∈Cm×n are indexed by elements of Zm and Zn, respectively. A(j,k), A(j,:), A(:,k), and AT represent entry (j,k), row j, column k, and transpose matrix of A, respectively. In∈Cn×n is identity matrix.


## 2. Background

### 2.1. Block Matrix Operations

A block matrixA∈Cmp×nq with m row partitions and n column partitions and a block vector x∈Cmp with m row blocks are defined as (1)A=A0,0⋯A0,n-1⋮⋱⋮Am-1,0⋯Am-1,n-1,x=x0⋮xm-1,respectively, where Aj,k∈Cp×q designates (j,k) block and xj∈Cp designates j block. In this paper, the following block matrix operations are used: Kronecker product, direct sum, stride permutation, vec operator, and vec inverse operator.The Kronecker product of two matricesA∈Cm×n and B∈Cp×q is defined as A⊗B∈Cmp×nq and it replaces every entry (j,k) of A by the matrix A(j,k)B. In the special case A=In, it is called parallel operation [12].The direct sum ofn matrices constructs a block diagonal matrix from a set of matrices, that is, for {Ck}k∈Zn, such that Ck∈Cpk×qn: (2)C=⨁k∈ZnCk=diag⁡C0,C1,…,Cn-1,where C∈Cp×q, p=∑j∈Znpj, and q=∑j∈Znqj.Letn=rs. The stride permutation matrix is defined as Lsn∈Cn×n such that it permutes the elements of the input signal x∈Cn as jr+k→ks+j, j∈Zs, and k∈Zr [12, 14]. This matrix permutation governs the data flow required to parallelize a Kronecker product computation [12]. We clarify that the superscript n is an index, not power.The vec operator,V:Cm×n→Cmn, transforms a matrix into a vector by stacking all the columns of this matrix one underneath the other. On the other hand, the vec inverse operator, Rm,n:Cmn→Cm×n, transforms a vector of dimension mn into a matrix of size m×n.


### 2.2. Discrete Fourier Transform

Letl2Zn be the set of C-valued signals on Zn; that is, x∈l2Zn if and only if x∈Cn [9]. Additionally, for each k1∈Z, x(k1)=x(k2), where k2∈Zn and k1≡k2mod⁡n. The discrete Fourier transform (DFT) of x∈l2(Zn) is represented as Fx:Zn→C such that Fx(k)=∑m∈Znx(m)ωN-mk, where ωn=exp⁡(2πi/n) and i=-1.As mentioned in [14], there are two different approaches of representing the DFT: as matrix-vector products or using summations. Consequently, fast algorithms using parallel computing are represented with either a matrix formalism as in [10, 12–14] or summations as in most signal processing books. Below, the matrix formalism is introduced and used to express the Cooley-Tukey FFT algorithm, corresponding to the decomposition of the transform size n into the product of two factors r and s; that is, n=rs.The matrix representation of DFT ofx is Fx=Fnx, where Fn∈Cn×n such that Fn(j,k)=ωN-jk. If n=rs, then the matrix formalism can be used to express Fn as factorizations of matrices using block matrices operations [10, 12, 13]:(3)Fn=LsnIr⊗FsLrnTrnIs⊗FrLsn.Here, Trn is a diagonal matrix containing the twiddle factors. We clarify that the superscript n is an index, not power. This factorization of Fn is the matrix representation of the Cooley-Tukey FFT for n=rs. In addition, this representation of Fn allows the implementation using parallel computing [14].


## 2.1. Block Matrix Operations

A block matrixA∈Cmp×nq with m row partitions and n column partitions and a block vector x∈Cmp with m row blocks are defined as (1)A=A0,0⋯A0,n-1⋮⋱⋮Am-1,0⋯Am-1,n-1,x=x0⋮xm-1,respectively, where Aj,k∈Cp×q designates (j,k) block and xj∈Cp designates j block. In this paper, the following block matrix operations are used: Kronecker product, direct sum, stride permutation, vec operator, and vec inverse operator.The Kronecker product of two matricesA∈Cm×n and B∈Cp×q is defined as A⊗B∈Cmp×nq and it replaces every entry (j,k) of A by the matrix A(j,k)B. In the special case A=In, it is called parallel operation [12].The direct sum ofn matrices constructs a block diagonal matrix from a set of matrices, that is, for {Ck}k∈Zn, such that Ck∈Cpk×qn: (2)C=⨁k∈ZnCk=diag⁡C0,C1,…,Cn-1,where C∈Cp×q, p=∑j∈Znpj, and q=∑j∈Znqj.Letn=rs. The stride permutation matrix is defined as Lsn∈Cn×n such that it permutes the elements of the input signal x∈Cn as jr+k→ks+j, j∈Zs, and k∈Zr [12, 14]. This matrix permutation governs the data flow required to parallelize a Kronecker product computation [12]. We clarify that the superscript n is an index, not power.The vec operator,V:Cm×n→Cmn, transforms a matrix into a vector by stacking all the columns of this matrix one underneath the other. On the other hand, the vec inverse operator, Rm,n:Cmn→Cm×n, transforms a vector of dimension mn into a matrix of size m×n.


## 2.2. Discrete Fourier Transform

Letl2Zn be the set of C-valued signals on Zn; that is, x∈l2Zn if and only if x∈Cn [9]. Additionally, for each k1∈Z, x(k1)=x(k2), where k2∈Zn and k1≡k2mod⁡n. The discrete Fourier transform (DFT) of x∈l2(Zn) is represented as Fx:Zn→C such that Fx(k)=∑m∈Znx(m)ωN-mk, where ωn=exp⁡(2πi/n) and i=-1.As mentioned in [14], there are two different approaches of representing the DFT: as matrix-vector products or using summations. Consequently, fast algorithms using parallel computing are represented with either a matrix formalism as in [10, 12–14] or summations as in most signal processing books. Below, the matrix formalism is introduced and used to express the Cooley-Tukey FFT algorithm, corresponding to the decomposition of the transform size n into the product of two factors r and s; that is, n=rs.The matrix representation of DFT ofx is Fx=Fnx, where Fn∈Cn×n such that Fn(j,k)=ωN-jk. If n=rs, then the matrix formalism can be used to express Fn as factorizations of matrices using block matrices operations [10, 12, 13]:(3)Fn=LsnIr⊗FsLrnTrnIs⊗FrLsn.Here, Trn is a diagonal matrix containing the twiddle factors. We clarify that the superscript n is an index, not power. This factorization of Fn is the matrix representation of the Cooley-Tukey FFT for n=rs. In addition, this representation of Fn allows the implementation using parallel computing [14].


## 3. DFT for Vector-Valued Signals

Based on [2, 6–9, 15, 16], the space of vector-valued discrete-time signals with n samples is defined as (4)l2Zn,Cd=x0,x1,…,xn-1T:xj∈Cd,j∈Zn.The space l2(Zn,Cd) is the set of Cd-valued signals on Zn; that is, x∈l2Zn,Cd if and only if x∈Cnd. Additionally, for each k1∈Z, xk1=xk2, where k2∈Zn and k1≡k2mod⁡n. Furthermore, if d=1, then l2(Zn,Cd)=l2(Zn). Now, for x∈l2Zn,Cd, there is a kind of DFT for vector-valued signals calledvector-valued DFT. This transform is defined as Fxd:Zn→Cd such that(5)Fxdk=∑m∈ZnWn-mkxm,where Wn∈Cd×d is the matrix kernel. Algorithm 1 shows the implementation of (5). This implementation is a sequential algorithm.Algorithm 1:Vector-valued DFT (sequential algorithm).
Require: x∈Cdn
Ensure: y∈Cdn
(1) for  k←0:n-1
(2) for  m←0:n-1
(3)  yk=yk+Wn-mkxm
(4) end for
(5) end forFrom the reviewed literature, there are two kinds of kernels for this transform: the first one ishypercomplex DFT kernel [8]: (6)Wn=exp⁡2πn·J=cos⁡2πn·Id+sin⁡2πn·J,where J∈Cd×d such that J2=-Id, and the second one isDFT frame kernel [7]: (7)Wn=1ddiag⁡ωnα0,ωnα1,…,ωnαd-1,where A={α0,α1,…,αd-1}⊂Zn with αj<αk for j<k. It is called DFT frame kernel because {ej}j∈Zn⊂Cd, where ej=(1/d)(ωnjα0,ωnjα1,…,ωnjαd-1)T is a DFT frame. In this paper, subsets A⊂Z+ are used, such that card⁡(A)=d, although it does not represent a DFT frame.Lemma 1.
LetWn∈Cd×d be a hypercomplex DFT kernel or DFT frame kernel. Then (1)
Wnj+r=Wnj·Wnr.(2)
Wn0=Wnn=Id.(3)
Ifk∈Z and r∈ZN, then Wnnk+r=Wnr.(4)
Ifn=rs, then Wnrk=Wsk.Proof.
For hypercomplex DFT kernel, the proof of each case is similar to proof ofnth roots of unity. For DFT frame kernel, Wn is a diagonal matrix, and then the proof of each case is straightforward.


## 4. A Parallel Framework forn=rs

In this section, the main results of this paper are presented. Firstly, a block matrix representation of the vector-valued DFT is given. Secondly, a new mathematical framework from matrix representation of vector-valued DFT is derived, using a block matrix formalism (i.e., Theorem2). This new result is inspired in the matrix representation of the Cooley-Tukey FFT algorithm for complex discrete-time signals, corresponding to the decomposition of the transform size n into the product of two factors r and s, which is developed in [10, 12, 13]. The result obtained in Theorem 2 is transformed in a new block matrix representation such that it contributes to analysis, design, and implementation of parallel algorithms (i.e., Corollary 3). This new result is inspired in (3). Finally, a computational complexity analysis of new algorithm is developed.Similar to the DFT matrix representation explained in Section2.2, there are two different approaches of representing the vector-valued DFT: as summations (see (5)) or using matrix-vector products. Both approaches allow a parallel implementation. In fact, the proof of Theorem 2 is developed using summation notation.The vector-valued DFT can be presented as matrix-vector products. The block matrix representation of vector-valued DFT ofx∈l2(Zn,Cd) is defined as Fxd=Fndx, where Fnd∈Cdn×dn such that (Fnd)j,k=Wn-jk∈Cd×d, for j,k∈Zn. We clarify that the superscript d is an index, not power. In this section, a block matrix factorization of Fnd is developed, and it is inspired in (3). First, a generalization of stride permutation is defined. Let n=rs. The block stride permutation matrix [14, 17] is defined as Lsn,d∈Cdn×dn such that Lsn,d=Lsn⊗Id, and, for each x∈Cdn with n blocks xj∈Cd, the operation Lsn,dx permutes each block of the input block x as jr+k→ks+j, j∈Zs, and k∈Zr.Theorem 2.
Letn=rs and let Fnd∈Cdn×dn be the block matrix of DFT for vector-valued signals. Then (8)Fnd=Fsd⊗IrTrn,dIs⊗FrdLsn,d,where Trn,d=⨁j∈ZsDrj such that Dr=⨁k∈ZrWn-k.Proof.
Letx∈Cdn, let l1,k1∈Zr, and let l2,k2∈Zs. The block vector y=(Is⊗Frd)Lsn,dx is defined. Then (9)yk2r+l1=∑k1∈ZrWr-k1l1xsk1+k2.Now, let z=Trn,dy. From Lemma 1, Wr-k1l1=Wn-sk1l1; then (10)zk2r+l1=Wn-k2l1yk2r+l1=Wn-k2l1∑k1∈ZrWn-sk1l1xsk1+k2=∑k1∈ZrWn-sk1l1+k2l1xsk1+k2.Let w=(Fsd⊗Ir)z. Then (11)wl1+l2r=∑k2∈ZsWs-k2l2zk2r+l1=∑k2∈ZsWs-k2l2∑k1∈ZrWn-sk1l1+k2l1xsk1+k2=∑k2∈ZsWn-rk2l2∑k1∈ZrWn-sk1l1+k2l1xsk1+k2=∑k2∈Zs∑k1∈ZrWn-rk2l2+sk1l1+k2l1xsk1+k2.But rk2l2+sk1l1+k2l1≡(k2+k1s)(l1+l2r)mod⁡n; then (12)wl1+l2r=∑k2∈Zs∑k1∈ZrWn-k2+k1sl1+l2rxsk1+k2=∑k2∈Zs∑k1∈ZrWn-k2+k1sl1+l2rxsk1+k2.Let m=sk1+k2, let k=l1+l2r, and let m,k∈Zn because l1,k1∈Zr, l2k2∈Zs, and n=rs. Then (13)∑m∈ZnWn-mkxm=Fxdk.Now, ifn=rs, A∈Cr×r, and B∈Cds×ds, the following equality [17] is obtained:(14)B⊗A=Lsn,dA⊗BLrn,d.From Theorem 2 and (14), the following corollary presents a matrix factorization of Fnd such that it permits an implementation using parallel computing.Corollary 3.
Letn=rs and let Fnd∈Cdn×dn be the block matrix of DFT for vector-valued signals. Then(15)Fnd=Lsn,dIr⊗FsdLrn,dTrn,dIs⊗FrdLsn,d,where Trn,d was defined in Theorem 2.Algorithm2 shows a parallel implementation of (15).Algorithm 2:Vector-valued DFT (parallel algorithm).
Require: x∈Cdn, where n=rs.
Ensure: y∈Cdn
(1)y←Lsn,dy
(2)A←Rdr,s{y}
(3)form←0:s-1
(4)A(:,m)←FA(:,m)d
(5)end for
(6)form←0:s-1
(7)A(:,m)←Drm⋅A(:,m)
(8)end for
(9)y←V{A}
(10)y←Lrn,dy
(11)A←Rds,r{y}
(12)form←0:r-1
(13)A(:,m)←FA(:,m)d
(14)end for
(15)y←V{A}
(16)y←Lsn,dyr independent processes in Steps (3)–(5), and 2s independent processes in Steps (6)–(8) and (12)–(14) are observed, making this approach a parallel operation. A model of Algorithm 2 is shown in Figure 1.Figure 1
Parallel model of vector-valued DFT forx∈l2Zn,Cd, n=rs, using a matrix representation.


### 4.1. Computational Complexity Analysis

In this section, the computational complexity analysis of (15) is developed. First, consider the matrix operation Lsn,dv. The computational complexity (CC) of Lsn,dv is O(nd) [8] because it is the multiplication between a block matrix in Cdn×dn and a block vector in Cdn. But the operation Lsn,dv can be implemented with a CC O(sd) (see, e.g., [12, 14]).LetFnd∈Cdn×dn be the block matrix and vector-valued signal x∈l2Zn,Cd, where n=rs. It is known that the CC of operation y=Fndx is O(n2d2)=O(r2s2d2). Now consider operation y=Fndx using (15). If we consider each matrix-vector multiplication, we obtain the following:(1)
The CC ofy1=Lsn,dx is O(sd).(2)
The CC ofy2=(Is⊗Frd)y1 is O(sr2d2), because it is a block diagonal matrix multiplication.(3)
The CC ofy3=Trn,dy2 is O(nd), because Trn,d is a diagonal matrix multiplication.(4)
The CC ofy4=Lrn,dy3 is O(rd).(5)
The CC ofy5=(Ir⊗Fsd)y4 is O(rs2d2), because it is a block diagonal matrix multiplication.(6)
The CC ofy=Lsn,dy5 is O(sd).Therefore, the CC of Fndx using (15) is (16)Osd+Osr2d2+Ond+Ord+Ors2d2+Osd=Osrr+sd2.Thus, the CC of operationFndx is O(r2s2d2) and the CC of operation Fndx using (15) is O(sr(r+s)d2). The above mentioned shows the efficiency of matrix formulation in (15).


## 4.1. Computational Complexity Analysis

In this section, the computational complexity analysis of (15) is developed. First, consider the matrix operation Lsn,dv. The computational complexity (CC) of Lsn,dv is O(nd) [8] because it is the multiplication between a block matrix in Cdn×dn and a block vector in Cdn. But the operation Lsn,dv can be implemented with a CC O(sd) (see, e.g., [12, 14]).LetFnd∈Cdn×dn be the block matrix and vector-valued signal x∈l2Zn,Cd, where n=rs. It is known that the CC of operation y=Fndx is O(n2d2)=O(r2s2d2). Now consider operation y=Fndx using (15). If we consider each matrix-vector multiplication, we obtain the following:(1)
The CC ofy1=Lsn,dx is O(sd).(2)
The CC ofy2=(Is⊗Frd)y1 is O(sr2d2), because it is a block diagonal matrix multiplication.(3)
The CC ofy3=Trn,dy2 is O(nd), because Trn,d is a diagonal matrix multiplication.(4)
The CC ofy4=Lrn,dy3 is O(rd).(5)
The CC ofy5=(Ir⊗Fsd)y4 is O(rs2d2), because it is a block diagonal matrix multiplication.(6)
The CC ofy=Lsn,dy5 is O(sd).Therefore, the CC of Fndx using (15) is (16)Osd+Osr2d2+Ond+Ord+Ors2d2+Osd=Osrr+sd2.Thus, the CC of operationFndx is O(r2s2d2) and the CC of operation Fndx using (15) is O(sr(r+s)d2). The above mentioned shows the efficiency of matrix formulation in (15).


## 5. Implementation and Experimental Investigation

### 5.1. General Information

The investigations have been carried out on a computer with multicore processor. The computer consists of 4 cores with Intel Core i7-3632QM CPU processor, system clock of 2.20 GHz, and 8 GB of RAM. The experiment develops the implementation and testing of Algorithms1 and 2 with the hypercomplex DFT kernel and the DFT frame kernel is developed. Algorithm 1 does not use any parallel implementation, unlike Algorithm 2. A CAZAC signal in l2(Zn,Cd) is used; it is generated using a Wiener CAZAC signal in l2(Zn) [9] with d=5 and n=rs, where n=1024=32·32, n=2048=64·32, n=4096=64·64, n=8192=128·64, and n=16384=128·128.The implementation of Algorithms1 and 2 to compute the vector-valued DFT is performed using MATLAB. Algorithm 2 is computed using Parallel Computing Toolbox. MATLAB uses built-in multithreading and parallelism using MATLAB workers. Parallelism using MATLAB workers is used. We can run multiple MATLAB workers (MATLAB computational engines) on a multicore computer to execute applications in parallel with the Parallel Computing Toolbox. This approach allows more control over the parallelism compared to built-in multithreading. With programming constructs, such as parallel-for-loops (parfor) and batch, we write the parallel MATLAB programs of the parallel framework for the vector-valued DFT.


### 5.2. Results and Discussion

LetT∗ be the execution time of Algorithm 1 without any parallel implementation, and let Tp be the execution time of Algorithm 2, where p is the number of cores. The value of Tp needs to be less than that of T∗ for two reasons: Algorithm 2 has a parallel implementation and the matrix multiplication size is different. Algorithm 2 is computed with matrices in Cdr×dr and Cds×ds. Algorithm 1 is computed with matrices in Cdn×dn, where n=rs.The computational performance analysis of Algorithm2 is evaluated using the metrics speedup (or acceleration) and efficiency. The speedup is the ratio between the execution times of parallel implementations with one core and parallel implementations with two or more cores [18]. The speedup is represented by the formula S=T1/Tp. The efficiency estimates how well utilized the processors are in solving the problem compared to how much effort is wasted in communication and synchronization [18]. The efficiency is determined by the ratio between the speedup and the number of processing elements, represented by the formula E=T1/(pTp).Table1 shows the execution time, in seconds (s), of both algorithms. A significant reduction in the parallel execution time of the vector-valued DFT is observed. Table 1 shows that Algorithm 1 with hypercomplex kernel for a Wiener CAZAC signal in l2(Z8192,C5) produces a time of serial execution T∗=13408 s. Using Algorithm 2, however, we obtain T1=106.7 (0.80% of T∗), T2=80.44 s (0.60% of T∗), T3=57.35 s (0.43% of T∗), and T4=32.67 s (0.24% of T∗). This result shows the advantage of using multicore processors and a parallel computing environment to minimize the high execution time in the vector-valued DFT. This is because parallel computing is a form of computation in which many calculations are carried out simultaneously [19, 20], operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently, and minimize the execution time [20, 21]. The difference between T∗ and Tp is because Tp is computed with matrices in Cdr×dr and Cds×ds. Algorithm 1 is computed with matrices in Cdn×dn, where n=rs.Table 1
Computing time of Algorithms1 and 2 (in seconds).
Kernel
p
n
1024
2048
4096
8192
16384
Hypercomplex DFT
∗
36.80
163.9
853.5
13408
+
15000
1
3.142
8.950
18.78
106.7
263.4
2
2.363
4.276
17.25
80.44
180.9
3
1.695
3.222
12.75
57.35
154.7
4
0.983
2.966
6.481
32.67
82.65
DFT frame
∗
40.50
173.1
881.0
13913
+
15000
1
2.438
9.749
20.97
95.29
251.6
2
1.911
5.798
16.38
58.72
179.5
3
1.531
5.126
12.33
57.40
151.4
4
1.199
2.329
5.366
31.46
73.42
Test signal inl2(Zn,Cd), where n=rs and d=5.
p
=
∗ is time execution of Algorithm 1.
p
>
0 is the number of cores.Table2 represents the speedup of Algorithm 2. The acceleration of the vector-valued DFT increases when p increases regardless of the value of n. The results show that, using the proposed parallel implementation with p cores, where p=2,3,4, the speedup to compute the vector-valued DFT of a Wiener CAZAC signal is 1.09, 1.47, and 2.99, respectively. These results imply that, to get the highest speedup, one should prefer the approach with four cores.Table 2
Speedup of Algorithm2.
Kernel
p
n
1024
2048
4096
8192
16384
Hypercomplex DFT
2
1.333
2.093
1.089
1.326
1.456
3
1.853
2.778
1.473
1.860
1.703
4
3.196
3.017
2.987
3.265
3.187
DFT frame
2
1.275
1.509
1.281
1.623
1.402
3
1.592
1.707
1.701
1.660
1.661
4
2.033
3.757
3.901
3.029
3.426
Test signal inl2(Zn,Cd), where n=rs and d=5.
p is the number of cores.Table3 represents efficiency of Algorithm 2. The information in this table shows that a good efficiency (greater than 65%) is reached with p=2. But the efficiency of the vector-valued DFT decreases (until 36%) when p increases regardless of the value of n. It is attributed to a decrease in the share of simultaneous computation of the partial vector-valued DFT in Algorithm 2 (steps (3)–(5) and (12)–(14)), which is responsible for the main effect. The results obtained in Table 3 imply that, to get a better efficiency, one should prefer the approach with two cores, because we obtain the highest efficiency.Table 3
Efficiency of Algorithm2.
Kernel
p
n
1024
2048
4096
8192
16384
Hypercomplex DFT
2
0.665
1.046
0.544
0.663
0.728
3
0.463
0.694
0.368
0.465
0.426
4
0.400
0.377
0.362
0.408
0.398
DFT frame
2
0.637
0.755
0.645
0.811
0.701
3
0.530
0.427
0.425
0.415
0.415
4
0.508
0.470
0.489
0.379
0.428
Test signal inl2(Zn,Cd), where n=rs and d=5.
p is the number of cores.


## 5.1. General Information

The investigations have been carried out on a computer with multicore processor. The computer consists of 4 cores with Intel Core i7-3632QM CPU processor, system clock of 2.20 GHz, and 8 GB of RAM. The experiment develops the implementation and testing of Algorithms1 and 2 with the hypercomplex DFT kernel and the DFT frame kernel is developed. Algorithm 1 does not use any parallel implementation, unlike Algorithm 2. A CAZAC signal in l2(Zn,Cd) is used; it is generated using a Wiener CAZAC signal in l2(Zn) [9] with d=5 and n=rs, where n=1024=32·32, n=2048=64·32, n=4096=64·64, n=8192=128·64, and n=16384=128·128.The implementation of Algorithms1 and 2 to compute the vector-valued DFT is performed using MATLAB. Algorithm 2 is computed using Parallel Computing Toolbox. MATLAB uses built-in multithreading and parallelism using MATLAB workers. Parallelism using MATLAB workers is used. We can run multiple MATLAB workers (MATLAB computational engines) on a multicore computer to execute applications in parallel with the Parallel Computing Toolbox. This approach allows more control over the parallelism compared to built-in multithreading. With programming constructs, such as parallel-for-loops (parfor) and batch, we write the parallel MATLAB programs of the parallel framework for the vector-valued DFT.


## 5.2. Results and Discussion

LetT∗ be the execution time of Algorithm 1 without any parallel implementation, and let Tp be the execution time of Algorithm 2, where p is the number of cores. The value of Tp needs to be less than that of T∗ for two reasons: Algorithm 2 has a parallel implementation and the matrix multiplication size is different. Algorithm 2 is computed with matrices in Cdr×dr and Cds×ds. Algorithm 1 is computed with matrices in Cdn×dn, where n=rs.The computational performance analysis of Algorithm2 is evaluated using the metrics speedup (or acceleration) and efficiency. The speedup is the ratio between the execution times of parallel implementations with one core and parallel implementations with two or more cores [18]. The speedup is represented by the formula S=T1/Tp. The efficiency estimates how well utilized the processors are in solving the problem compared to how much effort is wasted in communication and synchronization [18]. The efficiency is determined by the ratio between the speedup and the number of processing elements, represented by the formula E=T1/(pTp).Table1 shows the execution time, in seconds (s), of both algorithms. A significant reduction in the parallel execution time of the vector-valued DFT is observed. Table 1 shows that Algorithm 1 with hypercomplex kernel for a Wiener CAZAC signal in l2(Z8192,C5) produces a time of serial execution T∗=13408 s. Using Algorithm 2, however, we obtain T1=106.7 (0.80% of T∗), T2=80.44 s (0.60% of T∗), T3=57.35 s (0.43% of T∗), and T4=32.67 s (0.24% of T∗). This result shows the advantage of using multicore processors and a parallel computing environment to minimize the high execution time in the vector-valued DFT. This is because parallel computing is a form of computation in which many calculations are carried out simultaneously [19, 20], operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently, and minimize the execution time [20, 21]. The difference between T∗ and Tp is because Tp is computed with matrices in Cdr×dr and Cds×ds. Algorithm 1 is computed with matrices in Cdn×dn, where n=rs.Table 1
Computing time of Algorithms1 and 2 (in seconds).
Kernel
p
n
1024
2048
4096
8192
16384
Hypercomplex DFT
∗
36.80
163.9
853.5
13408
+
15000
1
3.142
8.950
18.78
106.7
263.4
2
2.363
4.276
17.25
80.44
180.9
3
1.695
3.222
12.75
57.35
154.7
4
0.983
2.966
6.481
32.67
82.65
DFT frame
∗
40.50
173.1
881.0
13913
+
15000
1
2.438
9.749
20.97
95.29
251.6
2
1.911
5.798
16.38
58.72
179.5
3
1.531
5.126
12.33
57.40
151.4
4
1.199
2.329
5.366
31.46
73.42
Test signal inl2(Zn,Cd), where n=rs and d=5.
p
=
∗ is time execution of Algorithm 1.
p
>
0 is the number of cores.Table2 represents the speedup of Algorithm 2. The acceleration of the vector-valued DFT increases when p increases regardless of the value of n. The results show that, using the proposed parallel implementation with p cores, where p=2,3,4, the speedup to compute the vector-valued DFT of a Wiener CAZAC signal is 1.09, 1.47, and 2.99, respectively. These results imply that, to get the highest speedup, one should prefer the approach with four cores.Table 2
Speedup of Algorithm2.
Kernel
p
n
1024
2048
4096
8192
16384
Hypercomplex DFT
2
1.333
2.093
1.089
1.326
1.456
3
1.853
2.778
1.473
1.860
1.703
4
3.196
3.017
2.987
3.265
3.187
DFT frame
2
1.275
1.509
1.281
1.623
1.402
3
1.592
1.707
1.701
1.660
1.661
4
2.033
3.757
3.901
3.029
3.426
Test signal inl2(Zn,Cd), where n=rs and d=5.
p is the number of cores.Table3 represents efficiency of Algorithm 2. The information in this table shows that a good efficiency (greater than 65%) is reached with p=2. But the efficiency of the vector-valued DFT decreases (until 36%) when p increases regardless of the value of n. It is attributed to a decrease in the share of simultaneous computation of the partial vector-valued DFT in Algorithm 2 (steps (3)–(5) and (12)–(14)), which is responsible for the main effect. The results obtained in Table 3 imply that, to get a better efficiency, one should prefer the approach with two cores, because we obtain the highest efficiency.Table 3
Efficiency of Algorithm2.
Kernel
p
n
1024
2048
4096
8192
16384
Hypercomplex DFT
2
0.665
1.046
0.544
0.663
0.728
3
0.463
0.694
0.368
0.465
0.426
4
0.400
0.377
0.362
0.408
0.398
DFT frame
2
0.637
0.755
0.645
0.811
0.701
3
0.530
0.427
0.425
0.415
0.415
4
0.508
0.470
0.489
0.379
0.428
Test signal inl2(Zn,Cd), where n=rs and d=5.
p is the number of cores.


## 6. Conclusion

This work presented a parallel framework of vector-valued DFT for vector-valued discrete-time signals. This mathematical framework was inspired in the matrix representation of the Cooley-Tukey FFT algorithm for complex discrete-time signals, corresponding to the decomposition of the transform sizen into the product of two factors r and s, which is developed in [10, 12]. It was expressed in (15) and Algorithm 2. This parallel framework was performed in terms of a matrix representation using a set of block matrix operations: Kronecker product, direct sum, stride permutation, vec operator, and vec inverse operator. These operations contributed to analysis, design, and implementation in parallel. Two kernels are used in the vector-valued DFT: hypercomplex DFT kernel and DFT frame kernel.The experimental investigation indicated there are profit using MATLAB with the Parallel Computing Toolbox in a computer with multicore processors. First, there was advantage to use multicore processors and a parallel computing environment to minimize the high execution time (with hypercomplex DFT kernel, we obtainedT∗=13408 s, T1=106.7, T2=80.44 s, T3=57.35 s, and T4=32.67 s). Second, speedup increased when p increased regardless of the value of n, and a good efficiency too was obtained when p=2 (above 65%).As future work, we would like to extend the proposed parallel framework to vector-valued discrete-time signals inl2(Zn,Cd), where n=2k, using the idea of Pease algorithm for complex discrete-time signals [22]. Additionally, we would like to take advantage of more design tradeoffs of different approaches besides what have been shown in this paper, for example, the approach developed in [23].



---

*Source: 348517-2015-09-15.xml*