6415 Ijdps 01
6415 Ijdps 01
6415 Ijdps 01
4, July 2015
ABSTRACT
One of the most significant challenges in Computing Determinant of Rectangular Matrices is high time
complexity of its algorithm. Among all definitions of determinant of rectangular matrices, Radics
N
definition has special features which make it more notable. But in this definition, C( ) sub matrices of the
M
order mm needed to be generated that put this problem in np-hard class. On the other hand, any row or
column reduction operation may hardly lead to diminish the volume of calculation. Therefore, in this paper
we try to present the parallel algorithm which can decrease the time complexity of computing the
determinant of non-square matrices to O(N ).
KEYWORDS
Parallel algorithm, Non-square determinant, Ascending sequence, Dictionary order.
1. INTRODUCTION
Determinant is one of the basic concepts in linear algebra and applied statistics that have major
applications in various branches of mathematics and engineering. Computing the determinant of a
matrix is a classical problem, which is addressed in normal forms of matrix studies [1-4] and
computational number theory [5].
In principle, determinant is only defined for square matrices [6]. There is usable and clear
definition for the calculation of square matrices determinant. A parallel algorithm for the
calculation of square matrix determinant is presented with time complexity ( ) [7]. But,
extracting data from physical phenomena and real world applications generally leads to produce
non-square matrices [8-10].
So far, many definitions for determinant of non-square matrices are given. Most of the works that
has been done, focusing on the definition and calculation the determinant of non-square matrices
by dividing them into square blocks [11][12] .[13]. In reference [12] Radic proposed an efficient
definition for determinant of non-square matrices that has most of the important properties of
square matrices determinant. Also, some other properties of Radics determinant and its
geometrical interpretations, involving polygons in the plan R2 and polyhedral in R3 are given
in[12][14-18].
DOI:10.5121/ijdps.2015.6401
International Journal of Distributed and Parallel Systems (IJDPS) Vol.6, No.4, July 2015
In [19], non-square matrices are converted to square matrices by summarizing, that leads to miss
some part of data.
The determinant of non-square matrix is used in retrieving images with different sizes [8]. Also,
there are some works on video retrieval and video shot boundary detection and image processing
by using determinant of non-square matrix [8][20-23]. Thus providing an effective solution for
calculating the determinant of non-square matrices can be very valuable and helpful.
In paper [24] a parallel algorithm based on pointer jumping technique is proposed to calculate the
determinant of non-square matrices of order 2 . But despite the successful work that has been
done for the definition of non-square matrices determinant, yet there isnt any efficient algorithm
to compute this determinant.
According to Radics definition for the determinant of a non-square matrix m n, it should be
n
calculated the determinant of C( ) square matrices from the order of m m. The square matrices
m
are obtained by combination of non-square matrix columns. Hence, the calculation of nonmatrices determinant is NP-hard. Some researchers [14] have tried decrease rows or columns of a
non-square matrix to convert it into a square matrix. But normally any change in rows or columns
of non-square matrices increase computation and column operations.
According to above explanation and proven theorems [12] currently, the only effective solution to
compute the determinant of non-square matrices by acceptable time complexity is parallel
algorithms.
To paralyze the algorithm, at first, the dependency between each Radics sub-square matrices
should be omitted. Secondly, each of these determinants also needs to be computed in parallel.
In this paper, we proposed a parallel algorithm to calculate the determinant of non-square
matrices based on Radics definition with O(n ) time complexity.
Problems and motivations are considered in Section 2. In Section 3 the Radics definition are
analyzed in details. Section 4 includes the proposed method to compute each arbitrary elements of
Dictionary order independently and in Section 5 a parallel algorithm for computing Raidcs
determinant is presented. The complexity of proposed algorithm is perused due to the hardware
architecture In Section 6. Section 7 clarifies our conclusions.
International Journal of Distributed and Parallel Systems (IJDPS) Vol.6, No.4, July 2015
In this paper we propose a novel approach for parallel production of square sub matrices which
reduces the time complexity to O(m (n m)).
('! , ' , , '* ) <+ (,! , , , , ,* ) ( > 0)(1 )('3 = ,3 )('5 <5 ,5 ). That is, if
one of the terms '5 <5 ,5 and all the preceding terms are equal.
Theorem 1:
Regarding to def.1, the maximum number of m-tuple sub sequences of ascendant set A =
n
{a! , a , , a6 } where m < , is equal to
.
m
Proof:
Putting the minimum element in the first place (as a! in set A), we would have n 1 choice for
the remaining m 1 places. In the same way, by selecting a , there will be n 2 selection for
the last m 1 places, and finally by putting '67"8! in the first place, there will be remained
m 1 choices for m 1 places. In other word, all the possible selections can be shown as
follow.
;<
67!
57!
;F
67
57!
:
p! , >?
= ?@?
, ,?A
=5
1:
:
p! , >?
= ?@?
, ,?A
=5
2:
A={a! , a , , aBCCCDCCCE
67"8! , , a 6 }
n-m+1:
;GHIJ<
:
p!
"
"7!
57!
, >?
= ?@?
, ,?A
=5
International Journal of Distributed and Parallel Systems (IJDPS) Vol.6, No.4, July 2015
According to the dictionary order and ascending sequences definition, its obvious that, for
m < , the first element of A = {1,2, , n} is [1,2, , m], which we entitled First Member. Also,
the last element in this sequence will be [n m + 1, n m + 2, , n] and the remaining sub
ascending sequences will be in this interval.
[1,2, , m] < [1,2, , m + 1] < < [n m + 1, n m + 2, , n]
n
Now, according to Theorem 1, the sequences can be numbered from 0 to
1. Also,
m
according to the latest member of ascending sequences the maximum value of each place is
determined. For example, the maximum value which the mth place can be obtained, is n, But due
to the need to establish the condition a "7! < a " , the value of (m-1)th place cannot exceed n-1.
In the following, we present Radic's definition for determinant of non-square matrices.
Definition 3. Let
= ['3,N ] be an
matrix with
'!N<
det( ) = !YN< ZZNUY*(1)P8Q (RS T
'5N<
where [! , [ , , [5 , ] = 1 + 2 + +
det( ) = 0.
'!NU
X,
'5NU
(1)
and ^ = [! + + [5 . If
Now, according to Definition 3 is observed that the following sub square matrices produced in
Radics definition is in accordance with the dictionary order. So, if an efficient algorithm can be
represented for the computation of dictionary order elements, therefore Radics determinant can
also be calculated with greater efficiency.
[=0
[=1
[=
[=
2
1
1=1
1
0
2
1
1=2
2
0
3
1
1
2
1
2
+1
1
1=
0
1
1=
3
2
2
1
2
2
1
1
1+[
a.
[
According to Table 1and as it mentioned in theorem 1, the weight of each element in the
Ascending sequence is equal the last column of the table.
As you can see in Table 1, each (j, i)th entries in the table is obtained from `
International Journal of Distributed and Parallel Systems (IJDPS) Vol.6, No.4, July 2015
nk+1
n1
n2
n3
nk
nm
,
, ,
,
,
, ,
3
c+1
1
2
c
0
m
1
2
3
k1
k
c+1
c
<d
, m k + 1 element of the First Member will change. We
c+1
c
use Table 1 to calculate the amount of the change. To this, according Table 1, we must go to left
c
is located. As can be seen in Table 1, the first element at the left
in the jth row where
c
c1
side of the start point is
.
c1
Now, if
Until condition d
c
+ +
c
c=
is satisfied, we continue the steps to the left.
c
Then the numbers of steps, which is moved to the left side in jth row, will be added to the value of
last m-k locations in the First Member. The new value of d is calculated from the following
equation.
c1
g
.
d d 3hi
c
International Journal of Distributed and Parallel Systems (IJDPS) Vol.6, No.4, July 2015
1=0
[=0
[=1
[=2
[=3
[=4
0
0
1
1
2
2
3
3
4
4
1=1
1
0
2
1
3
2
4
3
5
4
1=2
2
0
3
1
4
2
5
3
6
4
1=3
3
0
4
1
5
2
m+n
`
a
n
6
3
10
10
20
15
35
7
4
Table 3a
table 3b
We assume q = 49. In this case, according to table 3, the weight of each place in the First Member
would be as follows.
7 6 5 4 3
4 3 2 1 0
1 2 3 4 5
7
8
6
Since
<d<
, in the fifth row (j = 4) we will proceed to the left, but because
+
4
5
4
7
> 49 is not acceptable, so we stopped at p = 1. Therefore, p = 1 and the new q is equal to
4
7
q = 49
= 14 and
a
unit
will
be added
to
the fifth
last
places.
4
2 3 4 5 6
+ 1 1 1 1 1
2 3 4 5 6
5
4
+
s = 0, the algorithm has finished and 49th
3
3
element in the sequence of dictionary order is generated.
tu
= [2,5,6,7,8]
6
International Journal of Distributed and Parallel Systems (IJDPS) Vol.6, No.4, July 2015
It is proven for any arbitrary d, using combinatorial addition the whole dictionary ordered
elements are produced.
Theorem 2: Using combinatorial addition, by adding arbitrary d to First Member of the
<
will be generated.
= [1,2,3, ,
= x1,2,3, ,
1,
1, BDE
+ 1z
yh!
This is the second element in dictionary order. In other words, only one location was changed.
Inductive assumption:
Suppose using combinatorial addition to add d units to First Member. Thus, the ascending
vw
sequence 1,2,3, , '57y8! , '
BCCCCCDCCCCCE
57y , '57y7! , , '5 is produced, which is exactly the d
y
element in dictionary order. This sequence is obtained by changing at most c places of First
Member.
Inductive rule:
It should be shown that adding d + 1 units to First Member, the ( d + 1)vw element in the
dictionary order will be generated.
First case: Suppose by adding d + 1 to First Member, just c places have changed. Regarding the
inductive assumption, since only c places were changed, therefore, it is exactly the ( d +
1)vw element in the dictionary order.
,
'5
1,2,3, , '57y8!, '
BC
CC,C'C57y7!
CDCCC
CC,CE
57y
y
places. Because, all places achieve to their highest possible value. According to the dictionary
order, its clear the ( d + 1)vw element is 1,2,3, , BCCCCCCCCCDCCCCCCCCCE
c + 1, c + 2, , + 1.
y8!
We will show Combinatorial Addition exactly generated the same sequence. According to Table
1, the value is equal to
)
y
d = BCCCCCCCCCCCCDCCCCCCCCCCCCE
|y8*7(58!)
} + |y8*7(58
} + + |y7!
}
y7!
y7!
*75
International Journal of Distributed and Parallel Systems (IJDPS) Vol.6, No.4, July 2015
)
y
d + 1 = BCCCCCCCCCCCCDCCCCCCCCCCCCE
|y8*7(58!)
} + |y8*7(58
} + + |y7!
}+1
y7!
y7!
*75
Defined as Combinatorial Addition, the (c + 1)vw place has increased a unit and other elements
subsequently increased. So, the following ascending sequence is obtained.
1,2,3, , BCCCCCCCCCDCCCCCCCCCE
c + 1, c + 2, , + 1
y8!
International Journal of Distributed and Parallel Systems (IJDPS) Vol.6, No.4, July 2015
For i = 1 To (n - m+ 1)
A(1, i) = i
For i = 1 To m
A(i, 1) = 1
k = n - m+ 1
For i = 2 To m
For j = 2 To k
A(i, j) = A(i, j - 1) + A(i - 1, j)
j=1
For i = 1 To m
B(i) = i
Sum = 0, p = 0, i = k
While A(j, k) <= q
j=j+1
j=j-1
i=k
While Sum <= q
Sum = A(j, i) + Sum
p=p+1
i=i-1
Sum = Sum - A(j, i + 1)
p=p-1
B(m - j) = B(m - j) + p
For h = m - j To m - 1
B(h+ 1) = B(h) + p
q= q - Sum
j=1
k=k-p
p=0
Sum = 0
Wend
B(m) = B(m) + q
Fig 1: Pseudo code of generating arbitrary sequence
This algorithm can be implemented in various granularities. This means whatever the number of
processors is further, the granularities can be smaller. And we will have larger granularities if the
number of processors is less. In other words, if the number of processors is k, the number of
granularities will be
form
~
U
(y7!) U
to
to
*
5
y
U 7!
*
.
7!
5
to
~
U
7!
is for the second processor. In the same way, the last processor calculates
Pseudo-code for producing ascending sequence from a specific element
] = 1 S 5
1
y
(1) = (1) + 1
(1) > R
(1 c) = (1 c) + 1
1R (1 c) > c
c = c + 1
(1 c) = (1 c) + 1
R (
(c < ) R
9
International Journal of Distributed and Parallel Systems (IJDPS) Vol.6, No.4, July 2015
] = 1 c 1
( + 1) = () + 1
c = 1
(
(
R (
processors with
a CRCW memory, this algorithm can calculate the determinant of
non-square matrix
in ( ( ) + ) | ( )}.
If the memory is Concurrent Read Exclusive Write (CREW), the time required to sum the results
of all processors in tree structure will be equal to
. we know that ! ( ).
Thus the determinant of the non-square matrix will be calculated at ( ( ) + )
| ( )}.
In Exclusive Read Exclusive Write (EREW) memories, there is a burden to read matrices. If
enough memory is available, the matrix can be copied in a tree structure in
time
complexity. Then, it will be accessible for all processors. In this case, the algorithm complexity is
( ( ) + 2 ) | ( )}. Given the above description it has been shown that
the time complexity of the proposed algorithm is ( ).
Its obvious the proposed algorithm in cloud computing architecture and other architectures in
which processors are connected through the network tolerates the overhead of network too. So its
time complexity will be ( + RS]c_R]R'().
7. CONCLUSION
Using Parallel algorithms is an effective method for reducing the time complexity. However, in
most cases, increasing the number of processors does not increase productivity and just reduces
the required time. But given that the cost of producing complex hardware with many processors is
declining sharply, therefore the parallel algorithm can have appropriate efficiency.
On the other hand, time is an important factor in reducing the response time of real-time systems,
and it plays a key role in the success of such systems. Note that, also in the machine vision, time
is one of the important factors; the proposed algorithm can be very efficient and effective.
10
International Journal of Distributed and Parallel Systems (IJDPS) Vol.6, No.4, July 2015
8. FUTURE WORK
In recent years, researchers interest in Cloud computing and distributed processing. Since the
proposed algorithm can be implemented in distributed systems, implementation and computing
network overhead in these systems can be considered as future researches.
With regard to applications of the determinant of matrix in image and video processing, making a
proper hardware and implementing the proposed algorithm can be a suitable solution in computer
vision.
There are other definition for determinant of non-square matrices, these definition can be
investigated whether they can be parallelize or not and be compared with proposed algorithm in
this paper.
REFERENCES
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
Domich, P.D. & Kannan, R. & Trotter Jr. Hermite, L.E, (1987) "normal Form Computation Using
Modulo Determinant Arithmetic", Mathematics of Operations Research, vol. 12, No. 1, pp:5059.
Frumkin, M.A, (1977) "Time Algorithms In The Theory Of Linear Diophantine Equations", In
Fundamentals of Computation Theory, LNCS 56, Springer-Verlag, pp:386392.
Newman, M, (1972) "Integral Matrices. Academic Press,".
Storjohann, A, (2000) "Algorithms for Matrix Canonical Forms", PhD thesis, Institut fur
Wissenschaftliches Rechnen, ETH-Zentrum, Zurich, Switzerland.
Cohen, H, (1996) "A course in computational number theory", Springer-Verlag.
Kaltofen, E. & Villard, G, (2001) "Computing The Sign Or The Value Of The Determinant Of An
Integer Matrix, A Complexity Survey", Preprint submitted to ALA2001 JCAM Special issue.
Teimoori, H & Bayat, M. & Amiri, A. & Sarijloo, E, (2005) "A New Parallel Algorithm for
Evaluating the Determinant of a Matrix of Order n", Euro Combinatory, pp: 123-134.
Abdollahi, N. & Jafari, M. & Amiri, A, (2012) Retrieving Images in different sizes using
Determinant kernel for non-square matrices, National Conference on Artificial Intelligent in
Electrical and Computer Engineering (NCAI).
Amiri, A. & Abdollahi, N. & Jafari, M. & Fathy, M, (2011) "Hierarchical Key-Frame Based Video
Shot Clustering Using Generalized Trace", Journal of Innovative Computing Technology, SpringerVerlag Berlin Heidlberg, pp: 251-257.
Abdollahi, N. & Jafari, M. & Amiri, A. & Fathy, M, (2011) "Generalization of the Trace Kernel on
Non-Square Matrices and its applications in video retrieval," the 7th Iranian Machine Vision and
Image Processing Conference (MVIP), IUST.
Joshi, V.N, (1980) A Determinant for Rectangular matrices, Bull. Austral. Math. Soc., vol. 21,
pp:137-146.
Radic, M, (1969) A Definition of the Determinant of A Rectangular Matrix, Glasnik Matemaicki,
vol. 1, No. 21, pp: 17-22.
Arunkumar, M. & Murthy, S. & Ganapathy, G, (2011) "Determinant For Non-Square Matrices",
International J. of Math. Sci. & Engg. Appls. (IJMSEA), ISSN 0973-9424, vol. 5, No. V, pp: 389-401.
Radic, M. & Susanj, R, (1992) An Application of the Determinant of A Rectangular Matrix in
Discovering Some Properties of the Pentagon, Glas. Mat. Ser. III 27, pp: 217-226.
Radic, M, (2008) "Areas of Certain Polygons in Connection with Determinants of Rectangular
Matrices", Beitrage zur Algebra und Geometrie Contributions to Algebra and Geometry, vol. 49,
pp:71-96.
Radic, M, (1991) A Generalization of the Determinant of a Square Matrix and Some of Its
Applications in Geometry, Serbo-Croatian Matematika (Zagreb), vol. 20, pp:19-36.
Radic, M, (2005) "About A Determinant of Rectangular 2 n Matrix and Its Geometric
Interpretation", Beitrage Zur Algbera und Geometric Contributions to Algebra and Geometry, vol. 46,
pp:321-349.
Susanj, R. & Radic, M, (1994) "Geometrical Meaning of One Generalization of the Determinant of A
Square Matrix", Glasnik Matematicki, vol. 29, pp:217-234.
11
International Journal of Distributed and Parallel Systems (IJDPS) Vol.6, No.4, July 2015
[19] Amiri, A. & Fathy, M. & Bayat, M, (2010) "Generalization of Some Determinantal Identities for
Non-Square Matrices Based on Radics Definition", TWMS J. Pure Appl. Math, vol. 1, No. 2, pp:
163-175.
[20] Amiri, A. & Fathy, M, (2011) Generalization of Eigenvalue and Eigenvector for Non-Square
matrices based on Radics Determinant and its application to video retrieval, to appear in Journal of
Applied and Computational Mathematics (A&CM).
[21] Amiri, A. & Fathy, M, (2009) A Novel Video Retrieval System Using GED-based Similarity
Measure, International Journal of Signal Processing, Image Processing and Pattern Recognition,
vol. 2, No. 3, pp:99-108.
[22] Amiri, A. & Fathy, M, (2009) Video Shot Boundary Detection Using Generalized Eigenvalue
Decomposition, Lecture Notes In Computer Science, vol. 5593, pp:780-790.
[23] Zhou, S.K, (2004) Trace and determinant kernels between matrices, SCR Technical Report.
[24] Abdollahi, N. & Jafari, M. & Amiri, A. & Fathy, M, (2011) A New Parallel Algorithm for
calculating the Determinant of a non-square Matrix of Order 2n , 1st National Conference on Soft
Computing and Information Technology.
[25] Amiri, A. & Bayat, M. & Fath, M. & Tiemoori, H, (2005) Determinant Identities for Non-Square
Matrices Based on Radics Definition: Dodgson,Cauchy-Binet and Trahan, Euro Combinatory,
pp:123-134.
Authors
Neda Abdollahi was born in Zanjan, Iran, in 1985. She received the B.S. and M.Sc.
Islamic Azad University, Zanjan, Iran, in 2008 and 2011. In 2009, she joined Bina
Software Co., as a technical expert and science then she has been with Department of
Electronic and Computer Engineering, Islamic Azad University of Zanjan and Payame
Noor University and from 2012, she has been a Faculty member of Saeb University,
Abhar, Iran. Her research interests include Multimedia Retrieval, Software Modeling,
Machine Learning Methods, Object-Oriented Analysis and Design, Mobile Ad-Hoc
Networks, Distributed Systems, Micro Programming and Web Design.
Mohammad Jafari was born in Zanjan, Iran, in 1977. She received the B.S. and
M.Sc. Islamic Azad University, Zanjan, Iran, in 2003 and 2011. In 2001, he has started
his work as CEO of Bina Software Co., Zanjan, Iran. From 2006 to 2011, he was a
computer technical expert of information and planning unit of the Zanjan Broadcasting
Center. And science 2009, he has been with Department of Electronic and Computer
Engineering, Islamic Azad University of Zanjan and University of Applied Science
and Technology and Sufi University, Zanjan, Iran. his research interests include
Software Modeling, Data Base, Object-Oriented Design, Computer Networking,
Mobile Distributed Systems, Programming and Web Design.
Morteza Bayat received M.S. degree in 2002 from Institute for Advance Studies in
Basic Sciences (IASBS), Zanjan, Iran, in Applied Mathematics, and the Ph.D. degree
in Differential Equations in 2008 from IASBS. Since 2008, he has worked in the
Computer Engineering Department of Zanjan University as an Professor Assistant.
His research interests include Matrix Computations and Differential Equations.
Ali Amiri was born in Zanjan, Iran, in 1982. He received the M.S. degree in
Computer Engineering from Iran University of Science and Technology (IUST), in
2006, where he is currently pursuing Ph.D. degree in the IUST. His research interests
include video segmentation, video retrieval and summarization, Matrix Computation
and moving object detection and tracking.
12
International Journal of Distributed and Parallel Systems (IJDPS) Vol.6, No.4, July 2015
Mahmood Fathy, was born in Tehran, Iran, in 1959. He received the B.S. degree in
Electronic Engineering from Iran University of Science and Technology (IUST), in
1985, M.Sc. degree in Microprocessor Engineering from Bradford, UK, 1988 and
Ph.D. degree in Image Processing and Processor Design from UMIST, UK in 1991.
Since 1992, he has been with the IUST, where he is currently Associate Professor at
the Department of Computer Engineering. His research interests include Computer
networks, QOS , internet Engineering, Application of image processing in Traffic,
Computer Architecture for image processing, video processing applications,
Panorama, Supper resolution, video classification, video retrieval and summarization.
13