Time it takes to find a determinant

To make the point of how inefficient it is to find the determinant of a matrix by the cofactor method, I wrote a program in MATLAB to demonstrate this.  A google search for a program written in any language to find the determinant by using the cofactor method was not available beyond a 4×4 matrix.  So, I wrote one that finds the determinant of matrices of up to 12×12 order.

I ran the program on an Intel(R) Core(TM) i5-8500 CPU @3.00GHz PC.  Here is a table of the CPU time it took in seconds to find the determinant of a matrix as a function of its order.
______________________________________
Order of matrix               CPU Time to Find
Determinant (s)
______________________________________
6×6                                           0.015625
7×7                                           0.046875
8×8                                           0.203125
9×9                                           0.828125
10×10                                        5.14063
11×11                                       52.6406
12×12                                   623.953
______________________________________

If one continues to do this for a 25×25 matrix, it is estimated that it would take 8.1821198 \times 10^{17} seconds which is more than 25 billion years, and we all know that the estimated age of the universe is less at about 13.77 billion years.

The trend of the approximate time it takes to find the determinant of the next order of the matrix, nxn is approximately n times the time it takes to find the determinant of a (n-1)x(n-1) matrix.  For example, it took a time of 52.6406 seconds for finding the determinant of a 11×11 matrix, while it would be estimated to take approximately 12×52.6406=631.7 seconds for finding the determinant of a 12×12 matrix.  This is close to the 623.953 seconds it actually took.

The above approximate time calculations are in concurrence with the note written by Professor A.J. Wise in 1969, where he showed that the number of arithmetic operations required to evaluate a nxn determinant by cofactor method is given by [n!e]-2, and hence n!e for large n and the time it takes to find the determinant of the next order of the matrix, nxn is approximately n times the time it takes to find the determinant of a (n-1)x(n-1) matrix

Since the arithmetic operation required here are just addition, multiplication and subtraction, the computation time could be crudely estimated as 4Tn!e for large n, where T is the clock cycle time and we assume that an addition or a multiplication or a subtraction each use 4 clock cycle times.  Does it match?

For a 3.00 GHz machine, T={1}/({3 \times 10^9}) seconds to give an approximate time for a 12×12 matrix determinant calculation to be 4 \times {1}/{(3 \times 10^9)} \times 12! e = 1.736  seconds.  It is not even of similar order.  Many items go into calculating CPU time for a numerical algorithm, but to do a comparative analysis, these calculations are quite helpful.


This post is brought to you by

Advertisements

MOOC on Introduction to Matrix Algebra released

Introduction to Matrix Algebra is available as a MOOC now on Udemy. Of course, it is free! https://www.udemy.com/matrixalgebra/.  You will have a lifetime access to 177 lectures, 14+ hours of high quality content, 10 textbook chapters complete with multiple choice questions and their complete solutions.

Learning Objectives are

  • know vectors and their linear combinations and dot products
  • know why we need matrix algebra and differentiate between various special matrices
  • carry unary operations on matrices
  • carry binary operations on matrices
  • differentiate between inconsistent and consistent system of linear equations via finding rank of matrices
  • differentiate between system of equations that have unique and infinite solutions
  • use Gaussian elimination methods to find solution to a system of equations
  • use LU decomposition to find solution to system of equations and know when to choose the method over Gaussain elimination
  • use Gauss-Seidel method to solve a system of equations iteratively
  • find quantitatively how adequate your solution is through the concept of condition numbers
  • find eigenvectors and eigenvalues of a square matrix

_____________________________________________________

This post is brought to you by

Friday October 31, 2014, 11:59PM EDT, November 1, 2014 3:59AM GMT – Release Date for an Opencourseware in Introduction to Matrix Algebra

In a true Netflix style, on Halloween night, Friday October 31, 2014 at 11:59PM EST, we are releasing all resources simultaneously for an open courseware on Introduction to Matrix Algebra athttp://mathforcollege.com/ma/.  The courseware will include

  • 150 YouTube video lectures of total length of approximately 14 hours,
  • 10 textbook chapters,
  • 10 online multiple-choice quizzes with complete solutions,
  • 10 problem sets, and
  • PowerPoint presentations.

So set your calendar for October 31 for some matrix algebra binging rather than candy binging.  For more info and questions, contact Autar Kaw.

Chapter 1: Introduction 

Chapter 2: Vectors

Chapter 3: Binary Matrix Operations

Chapter 4: Unary Matrix Operations

Chapter 5: System of Equations

Chapter 6: Gaussian Elimination Method  

Chapter 7: LU Decomposition

Chapter 8: Gauss-Seidel Method

Chapter 9: Adequacy of Solutions

Chapter 10: Eigenvalues and Eigenvectors

________________________
This post is brought to you by

 

Rusty on Matrix Algebra

Eight years ago, the Florida legislature decided to reduce the number of credit hours it takes a state university student to graduate with an undergrad engineering degree. The number of credit hours were reduced from 136 to 128. One of the courses that got the ax in the Mechanical Engineering Department at USF was a 2-credit hour Linear Algebra course. There are many other universities in the nation that have done the same.

So how do students learn Linear Algebra when the course is one of the requirements for accreditation of engineering programs?

Some universities have bundled Linear Algebra course content into courses such as Quantitative Methods where students are expected, in many cases, to learn linear algebra, a programming language/computational system, and complex analysis. Other curriculums have dispersed the Linear Algebra content into different courses such as the topic of special matrices in Programming, simultaneous linear equations in Statics, and eigenvalues/eigenvectors in Vibrations, etc. Unless quality controls are introduced carefully, the content/depth of Linear Algbera in such courses can vary substantially between courses and instructors. Such control is impossible in metropolitan universities such as USF where a large proportion of students transfer from community colleges.

To have a resource that would be a self-explanatory as well as get the students exposed to Linear Algebra applications motivated me to write a simple Introduction to Matrix Algebra book. The book consists of ten chapters spanning fundamentals of matrix algebra, numerical methods for solving a set of equations, and a treatment of adequacy of solutions and eigenvalues.

Since 2002, the Introduction to Matrix Algebra book has been downloaded free of charge by more than 30,000 users from 50 different countries, and the feedback has been humbling and fulfilling.

Since April 2008, the book has also been made available for a nominal charge via lulu.com as a pdf file as well as a soft cover book. Proceeds from the book are allowing me to expand the book with more examples/problems and additional chapters.

Since my belief continues to embrace open and uncomplicated dissemination, eight individual chapters of the book in pdf form are still available free of charge. So one may ask the following question. Why should I buy the book when it is available free of charge? For answer to this question, click here

For more details about the book, visit the book website at http://autarkaw.com/books/matrixalgebra/index.html

This post brought to you by Holistic Numerical Methods: Numerical Methods for the STEM undergraduate at http://numericalmethods.eng.usf.edu