New Sequential and Parallel Division Free Methods for Determinant of Matrices

A determinant plays an important role in many applications of linear algebra. Finding determinants using non division free methods will encounter problems if entries of matrices are represented in rational or polynomial expressions, and also when floating point errors arise. To overcome this proble...

Full description

Saved in:

Bibliographic Details
Main Author:	Sharmila, Karim
Format:	Thesis
Language:	eng eng
Published:	2013
Subjects:	QA Mathematics
Online Access:	https://etd.uum.edu.my/3869/1/s92168.pdf https://etd.uum.edu.my/3869/7/s92168.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-uum-etd.3869
record_format	uketd_dc
institution	Universiti Utara Malaysia
collection	UUM ETD
language	eng eng
advisor	Ibrahim, Haslinda Othman, Khairil Iskandar
topic	QA Mathematics
spellingShingle	QA Mathematics Sharmila, Karim New Sequential and Parallel Division Free Methods for Determinant of Matrices
description	A determinant plays an important role in many applications of linear algebra. Finding determinants using non division free methods will encounter problems if entries of matrices are represented in rational or polynomial expressions, and also when floating point errors arise. To overcome this problem, division free methods are used instead. The two commonly used division free methods for finding determinant are cross multiplication and cofactor expansion. However, cross multiplication which uses the Sarrus Rule only works for matrices of order less or equal to three, whereas cofactor expansion requires lengthy and tedious computation when dealing with large matrices. This research, therefore, attempts to develop new sequential and parallel methods for finding determinants of matrices. The research also aims to generalise the Sarrus Rule for any order of square matrices based on permutations which are derived using starter sets. Two strategies were introduced to generate distinct starter sets namely the circular and the exchanging of two elements operations. Some theoretical works and mathematical properties for generating permutation and determining determinants were also constructed to support the research. Numerical results indicated that the new proposed methods performed better than the existing methods in term of computation times. The computation times in the newly developed sequential methods were dominated by generating starter sets. Therefore, two parallel strategies were developed to parallelise this algorithm so as to reduce the computation times. Numerical results showed that the parallel methods were able to compute determinants faster than the sequential counterparts, particularly when the tasks were equally allocated. In conclusion, the newly developed methods can be used as viable alternatives for finding determinants of matrices.
format	Thesis
qualification_name	Ph.D.
qualification_level	Doctorate
author	Sharmila, Karim
author_facet	Sharmila, Karim
author_sort	Sharmila, Karim
title	New Sequential and Parallel Division Free Methods for Determinant of Matrices
title_short	New Sequential and Parallel Division Free Methods for Determinant of Matrices
title_full	New Sequential and Parallel Division Free Methods for Determinant of Matrices
title_fullStr	New Sequential and Parallel Division Free Methods for Determinant of Matrices
title_full_unstemmed	New Sequential and Parallel Division Free Methods for Determinant of Matrices
title_sort	new sequential and parallel division free methods for determinant of matrices
granting_institution	Universiti Utara Malaysia
granting_department	Awang Had Salleh Graduate School of Arts & Sciences
publishDate	2013
url	https://etd.uum.edu.my/3869/1/s92168.pdf https://etd.uum.edu.my/3869/7/s92168.pdf
_version_	1776103626291281920
spelling	my-uum-etd.38692023-02-08T02:24:35Z New Sequential and Parallel Division Free Methods for Determinant of Matrices 2013 Sharmila, Karim Ibrahim, Haslinda Othman, Khairil Iskandar Awang Had Salleh Graduate School of Arts & Sciences Awang Had Salleh Graduate School of Arts and Sciences QA Mathematics A determinant plays an important role in many applications of linear algebra. Finding determinants using non division free methods will encounter problems if entries of matrices are represented in rational or polynomial expressions, and also when floating point errors arise. To overcome this problem, division free methods are used instead. The two commonly used division free methods for finding determinant are cross multiplication and cofactor expansion. However, cross multiplication which uses the Sarrus Rule only works for matrices of order less or equal to three, whereas cofactor expansion requires lengthy and tedious computation when dealing with large matrices. This research, therefore, attempts to develop new sequential and parallel methods for finding determinants of matrices. The research also aims to generalise the Sarrus Rule for any order of square matrices based on permutations which are derived using starter sets. Two strategies were introduced to generate distinct starter sets namely the circular and the exchanging of two elements operations. Some theoretical works and mathematical properties for generating permutation and determining determinants were also constructed to support the research. Numerical results indicated that the new proposed methods performed better than the existing methods in term of computation times. The computation times in the newly developed sequential methods were dominated by generating starter sets. Therefore, two parallel strategies were developed to parallelise this algorithm so as to reduce the computation times. Numerical results showed that the parallel methods were able to compute determinants faster than the sequential counterparts, particularly when the tasks were equally allocated. In conclusion, the newly developed methods can be used as viable alternatives for finding determinants of matrices. 2013 Thesis https://etd.uum.edu.my/3869/ https://etd.uum.edu.my/3869/1/s92168.pdf text eng public https://etd.uum.edu.my/3869/7/s92168.pdf text eng public Ph.D. doctoral Universiti Utara Malaysia Abeles, F.F. (2008). Dodgson condensation: The historical and mathematical development of an experimental method. Linear Algebra and its Application, 429, 429-438. Abdi, H. (2007) The Eigen-decomposition: eigenvalues and eigenvectors. In: Neil Salkind (Ed.) (2007), Encyclopedia of Measurement and Statistics. Thousand Oaks (CA): Sage. Akl, S. G., & Bruda, S. D. (2001). Improving a solution’s quality through parallel processing. Journal of Supercomputing, 19, 221-233. Akl, S. G., Meijer, H., & Stojmenovic, I. (1994). An optimal systolic algorithm for generating permutation in lexicographic order. J. of Parallel and Distributed Computing, 20(1), 84-91. Akl, S. G. , & Stojmenovic, I. (1992). A simple optimal systolic algorithm for generating permutations. In Albert Zomaya, Parallel Processing Letter Parallel Computing: Paradigms and Application(pp.639-670). London: International Thomson Computer Press. Almasi, G. S., & Gottlieb, A. (1989). Highly parallel computing. Redwood City: Benjamin-Cummings publishers. Alonso, L., & Schott, R. (1996). A parallel algorithm for the generation of a permutation and applications. Theoretical Computer Science, 159, 15-28. Anderson, R. J. (1990). Parallel algorithms for generating random permutations on a shared memory machine, ACM, 95-102. Anton, H. (2000). Elementary linear algebra(8th ed.). New York: John Wiley. Anton, H., & Busby, R.C. (2002). Contemporary linear algebra. New York: John Wiley. Aziz, A. I., Haron, N., Mehat, M., Jung, L.T., Mustapa, A. N., & Akhir, P. E. A. (2009).Solving traveling problem on cluster compute nodes. International Journal of Computers, 3(2), 260-269. Bankier,J. D. (1961). The diagrammatic expansion of Determinants. The American Mathematical Monthly, 68(8), 788-790. Bernstein, D. S. (2008). Matrix mathematics(2nd ed.). New Jersey: Princeton University Press. Barisenko, A. A., Kalashnikov, V. V., Kulik, I. A., & Goryachev,O. E. (2008). Generation of permutations based upon factorial numbers, IEEE, 57-61. Brawer, S. (1989). Introduction to parallel programming. Academic Press, Inc. Bressoud, D. M., & Propp, J. (1999). How the alternating sign matrix conjecture was solved.Notices of AMS, 46, 637-646. Brestscher, O. (2009). Linear algebra with applications(4th ed.). New Jersey:Prentice Hall International. Burrage, K. (1995). Parallel and sequential method for ordinary differential Equation. New York: Oxford University Press Inc. Chalmers, A. & Tidmus, J. (1996). Practical parallel processing, an introduction to problem solving in parallel. London : International Thomson Computer Press. Cong, G., & Bader, D. A. (2006). An empirical analysis of parallel random permutations algorithm on SMPs. Technical Report, Georgia Institute of Technology. Dodgson, C. L. (1866). Condensation of determinants, being a new and brief method for computing their arithmetic Values. Proc. Roy. Soc. Ser. A 15, 150-155. Djamegni, C. T., & Tchuent�e, M. (1997) A cost-optimal pipeline algorithm for permutation generation in lexicographic order. J. of Parallel and Distributed Computing, 44(2), 153-159. Fadlallah, G., Lavoie, M., & Dessaint, L-A. (2000). Parallel computing environments and methods. IEEE, 2-7. Fike, C. T. (1975). A permutation generation method.The Computer Journal, 18(1), 21-22. Gao, J., & Wang, D. (2003). Permutation generation: Two new permutation algorithms. Retrieved from http://arxiv.org/abs/cs/0306025. on September 2008. Gentleman, W. M., & Johnson, S. C. (1974). The evaluation of determinants by expansion by minors and the general problem of substitution. Mathematics of Computation, 28(126), 543-548. Gentleman, W. M., & Johnson, S. C. (1976) . Analysis of algorithms, a case study: Determinants of matrices with polynomial entries. ACM Transactions on Mathematical Software, 2(3), 232-241. Goldberg, D. (1991). What every computer scientist should know about floating point arithmetic, ACM Computing Surveys, 21(1),5-48. Goldfinger, Y. (2008). Determinant by cofactor expansion using Cell processor. Retrieved on December, 2008 from http://mc2.umbc.edu/docs/goldfinger.pdf on 16/11/2008. Grama, A., Gupta, A., Karypis, G. & Kumar, V. (2003). Introduction to parallel computing(2nd ed.). Essex: Addison-Wesley. Griss, M. L. (1976). An efficient sparse minor expansion algorithm. Proceedings of ACM annual conference, Houston, Texas, United States, 429-434. Gropp, W., Lusk, E. & Skjellum, A. (1997). Using MPI portable parallel programming with the message-passing interface(2nd ed.). London: MIT Press. Gupta, P., Agarwal, V., & Varshney, M. (2008). Design and analysis of algorithms. New Delhi: Prentice-Hall of India Hajrizaj, D. (2009). New method to compute the determinant of a 3 � 3 matrix. International J. Algebra, 3, 211-219. Hanly, J. R., & Koffman, E. B. (2004). Problem solving and program design in C. (4th ed.). Boston: Pearson Addison-Wesley. Hanus, P. H. (1886). An elementary treatise on the theory of determinants. Boston: Gin and Company. Retrieved from http://archive.org/stream/elementary treati00hanuuoft#page/4/mode/2up. Harville, D. A. (1997). Matrix algebra from a statistician’s perspective. pp.179- 208. New York : Springer-Verlag. Hasiung, C. Y., & Mao, G. Y. (1998). Linear algebra. London: World Scientific Publishing. Heap, B. R. (1963). Permutations by interchanges. Computer J. 6, 293-294. Horowitz, E., Sahni, S., & Rajasekaran, S. (2008). Computer algorithms/C++ (2nd ed.). New Jersey: Silicon Press. Horowitz, E., & Sahni, S. (1975). On Computing the Exact Determinant of Matrices with Polynomial Entries.Journal of the ACM, 38-50. Huang,T. C., Shiu, L.C., & Huang, J. H. (2001). Efficient local memory sequence generation for data parallel programs using permutation. Journal of Systems Achitecture, 47, 505- 515. Hussain, S. J., & Ahmed, G. (2005). A comparative study and analysis of PVM and MPI for parallel and distributed systems. IEEE, 183-187. Ibrahim, H., Omar, Z., & Rohni, A. M. (2010). New algorithm for listing all permutations. Modern Applied Science , 4(2), 89-94. Iqbal, K. (1995). An algorithm for computation of determinants of polynomial matrices. Proceeding of the American Control Conferences, 2536-2537. Iyer, M. (1995). Permutation generation using matrices. Dr.Dobbs Journal. Retrieved from http://www.ddj.com/184409671. on December 2008. Johnson, L. W., Riess, R. D. & Arnold, J. T. (2002). Introduction to linear algebra (5th ed.). New York: Addison-Wesley Publishing Co. Jones, M. A. (20055). Determinant Algorithm generation with numlists. Dr.Dobbs Journal. Retrieved from http://www.ddj.com/184402006. on 14 Februrary 2010. Kaltofen, E. (1992)On computing Determinant of matrices without divisions. ACM, 324-349. Khattar, D. (2010). The Pearson guide to complete mathematics for AIEEE. (3th ed.). India :Pearson Education. Knuth, D. E. (2002). The art of computer programming, vol.4, New York: Addison-Wesley: Kokosi�nski, Z. (1990). On generation of permutations through decomposition of symmetric groups into cosets. BIT, 30, 583-591. Krattenthaler, C. (1999). Advanced determinant calculus. Sminaire Lotharingien Combin. 42,B42q, 1-67. Retrieved from http://www.mat.univie. ac.at/slc/wpapers/s42kratt.pdf on September 3008. Langdon, G. G. (1967). An Algorithm for generating permutations. Communication of ACM, 10(5), 298-299. Lee, H. R., & Saunder, B. D. (1995). Fraction free gaussian elimination for sparse matrices, Journal of Symbolic Computation, 19(5), 393-402. Leopald, C. (2001). Parallel and distributed computing, a survey of models, paradigm, and approaches. New York : John Wiley & Sons. Levitin, A. (2007). Introduction to the design & analysis of algorithms(2nd ed.). New York: Addison-Wesley. Lewis, T. G., & El-Rewini, H. (1992). Introduction to parallel computing. New Jersey: Prentice-Hall. Li, K. (2010). Fast and highly scalable parallel computations for fundamental matrix problem on distributed memory systems. The Journal Supercomputing, 271-297. Li, Y. (2009a). An explicit construction of Gauss-Jordan elimination matrix. Retrived from http://arxiv.org/abs/0907.5038. on 17.Mac.2011. Li, Y. (2009b). An effective hybrid algorithm for computing symbolic determinants. Applied Mathematic and Computation, 2495-2501. Lin, C., & Snyder, L. (2009). Principles of parallel programming. Boston: Pearson Addison-Wesley. Lin, C. (1991). Parallel permutation generation on linear array. International Journal of Computer Mathematic, 38, 113-121. Lipski, W., & Warsaw, J. (1979). More on permutation generation method. Computing, 357-365. Luyang, L., Hongtao, W., & Jianying, Z. (2006). Architeture singularity analysis for a class of parallel manipulators. Proceeding of International Technology and Innovation Conference 2006, 2003-2006. Mahajan, M. & Vinay, V. (1997). Determinant: Combinatorics, algorithms and complexity. Chicago Journal of Theoretical Computer Science, 730-738. Mohd Saman, M. Y., & Evans, D. J. (1995). Top-down for finding optimal grain size of parallel tasks. Pertanika J. Scince& Technology,3(2),241-259. Muir, T. (1933).A treatise in the theory of determinants. Ney York: Dover Publications. Ord-Smith, R.J. (1970). Generating of Permutation Sequences: Part 1. The Computer Journal, 13, 152-155. Osborn, R. (1960). Concerning fourth-order determinants. The American Mathematical Monthly, 67(7), 682-683. O’Connor, J. J., & Robertson, E. F. (1996). Matrices and determinants. Retrieved from (http://www-history.mcs.st-andrews.ac.uk/HistTopics/ on September 2008. Pacheco, P. S. (1997). Parallel programming with MPI. San Francisco: Morgan Kaufmann Publisher. Pavlovic, S. V. (1961). On the generalisation of the Sarrus’s Rule. Mathematika I Fizika, No.54, pp.19-23. Retrieved from http://pefmath2.etf.bg.ac.yu/files/40/54.pdf . on December, 2008. Peng, T., Jian, M., & Dong-Ma, Z. (1999). Application of the simulated annealing algorithm to the combinatorial optimisation problem with permutation property: An investigation of generation mechanism. European Journal of Operational Research , 81-94. Perry, W. L. (1988). Elementary linear algebra. New York: McGraw Hill Inc. Quinn, M. J. (2004). Parallel programming in C with MPI and OpenMP. New York : Mc Graw Hill. Reek, K. A. (1998). Pointers on C. Massachusetts: Addison-Wesley. Reffgen, A. (2003). The determinant in finite and infinite-dimensional vector spaces(Unpublished master dissertation). Matematiska institutionen, Lund University, Sweden. Rezaee, H., & Rezaifar,O. (2007). A new approach for finding the determinant of matrices. Applied Mathematics and Computation, 188, 1445-1454. Rice, A., & Torrence, E. (2006). Lewis Carrol’s condensation methods for evaluating determinants. Retrieved from http://www.MAA.ORG/MATHHORIZONS. 12-15. Rolfe, T. J. (2008) . The assignment problem: Exploring paralleism(1). Bulletin of ACM SIG on Computer Science Education. Rote, G. (2001). Division-free algorithms for the determinant and the Praffian: Algebraic and combinatorial approaches. Computational Discrete Mathematics, 119-135. Sasaki, T., & Kanada, Y. (1981). Parallelism in algebraic computation and parallel algorithms for symbolic linear systems. Proceeding of the AMC on Symbolic and Algebraic Computation, 160-167. Sasaki, T., & Murao, H.(1982). Efficient Gaussian elimination method for symbolic determinants and linear systems. ACM Trans. Math. Software , 8/3, 277-289. Scott, R. F. (2009). A Treatise of the theory of determinants. BiblioBazaar. Schneider, H., & Barker, G. P. (1989). Matrices and linear algebra. New York: Dover publications inc. Scneider, M. D., Steeg, M. & Young, H. F. (1982). Linear algebra. New York: Macmillan Publishing Co. Sedgewick, R. (1977). Permutation generation methods. Computing Surveys, 9(2), 137-164. Sedgewick, R. (2002). Permutation generation methods. Talks Dagstuhl Workshop on Data Structures, Wadern, Germany, February, 2002. Retrieved from http://www.cs.princeton.edu/ rs/talks/perms. pdf. on December, 2008. Sengupta, R. (1997). Cancellation is exponentially powerful for computing the determinant. Information Processing Letters, 62, 177–181. Shin, D. W. (2002). The permutation algorithm for non-sparse matrix determinant in symbolic computation. Proceeding on the 15th CISL winter workshop, Japan. Retrieved from http://icat.snu.ac.kr:3333/ww/pdf/ww200210/pdf. on November 2008. Simon, C. P., & Blume, L. E. (1994). Mathematics for economists. Chapter 7. W. W. Norton & Company: New York. Smit, J. (1979). New recursive minor expansion algorithmd, a presentation om a comparable context. Lecture Notes In Computer Science, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, 72, 74- 87. Soltys, M. (2002). Berkowitz’s algorithm and clow sequences. The electronic Journal of Linear Algebra, Vol.9, 42-54. Standish, T. A. (1997). Data structures, algorithms & software principles in C. New York : Addison-Wesley Publishing. Stojmenovic, I. (2006). Listing combinatoric objects in parallel. The International Journal of Parallel, Emergent and Distributed Systems, 21(2), 127-146. Teimoori, H., Bayat, M., Amiri, A. & Sarijloo, E. (2005). A new parallel algorithm for evaluating the determinant of a matrix of order n[PowerPoint slides]. Retrieved from http://www.math.tu-berlin.de/EuroComb05/Talks/Poster. on December 2008, Thongchiew, K. (2007). A computerize algorithm for generating permutation and it’s application in determining a determinant. Proc.of World Academy of Science, Engineering and Technology, 21 , 178-183. Tsay, J. C., & Lee, W. P. (1994). An systolic design for generating permutations in lexicographic order. Parallel Computing, 20(3), 353-361. Umeda, Y., & Sasaki, T. (2006). Computing determinants of rational functions. AGM SIGSAM Bulletin, 40(1), 2-8. Vein, R., & Dale, P.(1999). Determinants and their applications in mathematical physics. New York: Springer Verlag. Vieira, R. S. (2010). A new Algorithm for determinant evaluation-the reduction method. Retrieved from http://arxiv.org/PScache/arxiv/pdf/ 1012/ 1012.1790v2.pdf. on 8 March 2011. Viktorov, O. V. (2007). Permutation generation algorithm. Asian Journal of Information Technology, 6(9), 956-957. Wells, M. B. (1961). Generations of permutations by transposition. Math Comp., 15,192-195. Wilde, C. (1988).Linear algebra. Massachusetts: Addison-Wesley Publishing Co. Wilkinson, B., & Allen, M. (2005).Parallel programming. techniques and application using networked workstations and parallel computers(2nd ed.). New Jersey : Pearson Prentice-Hall. Zaks, S. (1984). A new algorithm for generation of permutations. BIT, 24, 196-204.

New Sequential and Parallel Division Free Methods for Determinant of Matrices

Similar Items