C/C++ Math Library - 5 - More Efficient Matrix Determinants

all right welcome back everyone um I Pro I said I would continue with the big integer stuff but I I I was just

so deep in uh I I was actually balls deep in looking at uh making the determinant algorithm more efficient so I figured it out somehow and um today

we're going to look at that um and then we'll continue on with IG integers next time I believe um so I guess we'll just hop

right into it um okay so if we look at our uh existing um our existing um algorithm

that we have for the determinant what we'll find is that it's super inefficient in terms of runtime

and memory it actually allocates both actually um because what we have is this Matrix uh let's say we have it's a

4x4 2 three 2 4 3 1 32 3 3 3 4 and then last

row so for each determinant that we're finding we're essentially going to be we splice The Matrix but we're not keeping the same Matrix we are copying it over so we're

creating how many how many matrices well we have a 3X3 the first one would be 2 two

2 3 2 4 and then 32 three or sorry 32 4 two I'll just do

those and then this also generates three more matrices because we have to get the 2x two matrices there so this we get um 3

three and then this will generate even more matrices the 43 and then the

44 so for each Matrix you're getting the how many of so this is this is a 4x4 here and you're going to get four

different matrices four new matrices here and then we have a 3 Y3 and that gives us three more and

then holy [ __ ] goddamn um so we're essentially calling n factorial we're creating n factorial matrices where n is the number of rows or the number of

columns um and how many operations this is taking well it's taking uh oh what is that taking actually that's a wonderful

question um well it does we have uh it's a great question actually um it's just but it's en it's enormous and the amount of memory this takes is is

pretty stupid um so it turns out that there is a better a much better way to do this without splicing matrices and that involves using excl something called exclusion lists it's it's it's

not like a computer science concept per se um but I just call it an exclusion list because

um because um let me just make sure I'm trans yeah um I call it an exclusion list because it it it we're telling the

compiler or the program which columns to ignore so let's we'll kind of walk through this in the way that I kind of piece this together but let's say we

have the same Matrix this determinant of the Matrix m is going to

equal the element at 1 one times the determinant um expanding across row two and we're

going to cancel or cut off Row one um so that's Matrix this element right here 1 one and then we cut

off the first row so we expand on the second row now um and then we cut off the First Column um so let me just move this over here

actually um so this is that's that then we'll have M * 1 2 and this is time the determinant will expand across row two

and cut off row or Cut Off column two then same thing plus M13 times the determinant expanding

across row two and cutting off Row three or column 3 and then minus M14 times the determinant expanding

across row two and uh cutting off column 4 so we're essentially cutting off the column of the element that we're accessing

um now however you can't just it's not this simple because um let's say that it would be hard just to do this

without having a list of excluded columns because if you remember when we spliced matrices if we spliced this first one here um we would get the that the First

Column is gone we can't access it anymore in the copy however in if we're we're just passing in m to all these determinant functions we're still going to have access to that First Column

which may complicate things um so we're going to have to have a list of columns to exclude so rather than taking up n factorial matrices has n factorial

matrices um we're now going to have um with the exclusion list we're going to have one

Matrix plus one list of size n um and the reason why it's going to be size n is because you can only exclude all the columns you can't exclude any more well it's actually going to be n

plus one for us just because of one thing that I'm going to add in the code but doesn't make too much of a difference um so rather than

having we essentially have um n by n + n + 1 as opposed to n n factorial

elements or and I don't even know how many elements that is because it's so many um but regardless it's going to be a lot um so if we follow this path

further we're going to go into determinant uh 21 and we're going to exclude column 1 here and this is going to equal

to expand across row two Cut Off column one M22 times the determinant expand across Row 3 now since we're cutting off the

Matrix even further uh and this time we're we're canceling out row two again then minus M23 times the determinant expand across

the next row row three and cut off the current column which is column 3 and then plus M uh 24 times the

determinant expanding cross uh row row three and cutting off column 4 um so now we are going in further oops

what just happened then determinant of 32 is going to equal to m33 but first let's do the exclusion

columns um so if we were just to take the second column as something to exclude we would not be excluding the first one however however we have to carry that exclusion all the way down

otherwise we're not calculating it properly so we have an exclusion of one and two here um so now uh the determinant here

it's going to be m33 times the determinant of three of 44 excuse

me um minus or 43 because we're cutting off column 3 sorry then minus uh M at

34 times the determinant expanding across row four and cutting off column 4 now let's go one level down again

determinant of 43 is going to equal m at 44 and that's it because that's the last element and this time our exclusion list looks like 1 2 and three because we're

cutting off column 3 and we're left with column 4 and then similarly determinant of column or 44 is going to equal m of

four three because we are excluding 1 two and four this time so the last remaining one is three um you can keep this going for you can do this whole

process out but you'll get the final answer after some point and this exclusion column list will kind of act like a stack in some ways um and we're

going to somewhat treat it like that uh the the differen is in the code will actually have a a fixed size so we'll have n plus one elements and we will just modify how many elements we want to

read from that list all right um yeah um so just one more quick note uh

or just notice how the parameters here uh I kept stating expanding across this row uh the parameter that you pass in here will be the row that you expand ac

across um and then the second parameter will be the next column to skip um from

y um all right so let's get right into the code I guess um let me find this all right we're going to have uh

add a few utility methods first um just for array a or array accessors I'm I'm going to Define them in C

mathematics. um it will return Boolean

mathematics. um it will return Boolean the first one and it's going to be contains uint and we're going to pass in unsigned integer pointer array and

uh an unsigned int number of elements and then the Target and then also just want to print

so void print uint array um pass an unsigned integer pointer array and the unsigned integer number of

elements um so you can just copy these definitions and then in C mathematics. C

create that file if you you don't have it just paste the definitions in and um these will be pretty simple we will go

linearly through the list um since you saw that sometimes it wasn't sorted or you will you will get that it's not sorted all the time uh like you might

have when we specifically when we call determinant 42 you'll have a list that looks like 132 which is not sorted so we cannot assume that this list is sorted

um okay um so for contains uint we're just going to iterate through the elements for unsigned int I is equal to z i is less than number of elements I

++ oops there we go um if array at I is equal to Target return true and then outside of the loop we're going to return false because we have not found

the elements then for print um we'll print it like a vector where we have the square brackets at in the

beginning uh then for the unassigned integer I is equal to zero I is less than number of elements I ++ uh we

will print F uh percent D for an integer and then a space after and then pass in the array at I as the argument and then at the end

just print uh closing square bracket and a new line just like that um and then now that we have actually written source code in the c

mathematics. c we have to add it to the

mathematics. c we have to add it to the Run path um so you can just type in C

mathematics. C uh when we type in all

mathematics. C uh when we type in all the the source file in um source file names in the batch files

nice okay um so the way we're going to implement this in code is going to be um I'm just going to go find the method here um we are going to have a new method and I'm going to call it it will

return float and I'll call it determinant exclusion we're going to pass in four different parameters I believe yeah or yeah four parameters we'll have the

Matrix pointer M uh then we will have an unsigned int row or this is actually going to be five

parameters so the row to expand upon then unsigned in call the new column to skip and then we're going to passing the array and the number of elements so

unsigned in pointer skip calls so this is just the array and then an unsigned int pointer um number of skip calls and the reason why it's a pointer

is because uh we want to modify it directly um like I said this is going to be a stack um and we want to we want to keep

track of it throughout um as we go back and forth so just write it like that and then in the determinant method you can just update the parameter to be

a pointer to M um so once again expand expansion row column to skip then the array to that we of columns that we're going to skip and

then the actual number of skipped columns all right you can copy this uh signature into matrix.

c um and then in um in the current Matrix uh method that we

have um you can just comment everything out because we're not going to use it um all right you know we'll actually just write the the new determinant

method right now so in determinant this will be the first call to determinant exclusion we're going to say if m. rows

does not equal m do calls or m. rows is

equal to Z we're going to return 0.0 float and then apart from that outside of the statement we're going to say return determinant exclusion pass in M

the pointer the row will be zero the column will be zero skip calls will be null and then the number of columns to skip will be also will be zero all right so that's what it should

look like make sure that m is a pointer now on the parameter list for determinant okay now in the actual determinant exclusion

method uh we're going to have a few things here we we will start with the array initialization uh so notice here how we pass in null and if that is the

case then we want to initialize AR the array um we can just do this by saying if not skip calls that means if the pointer is

null um we will initialize the array um so skip calls is equal to the malok of and we're going to say m. calls plus

one and once again the Plus One will be uh for the zero for the initial zero be passing because in the first round we have four columns and we don't want to skip any of them when we're when we're

expanding so we're just going to pass into zero and have that kind of as a ghost column to skip um but we won't actually be skipping a column

um so M do calls plus one and then we will multiply this by the size of unsigned int actually I don't think we

need let's see one two four oh we actually don't need to have that plus one in there because we don't and actually skip every single

column right yeah we don't skip every single column we only skip every column but one and that's that's the base case where we

return the single element okay well yeah so you only need the number of columns um then we also have to initialize the counter so number of skip

calls is equal to malok since it's a pointer we have to allocate memory then that's just a size of unsigned in uh and then we will initialize number of skip columns to zero to do this you

have to dreference number of skip skip calls and then just set it equal to zero uh now we're going to insert the current column into the

list um we do this we will say skip calls and then in square brackets for the index D reference of number of skip calls make sure you D reference it because we want the integer value not

the pointer value um is equal to call that's going to be the the the next element in the array and then pointer of number skip calls so we dreference

number skip calls and then you put the dreference in parenthesis and then just say plus plus um so let me actually diagram why this works this

way um so let's uh is there a way to there we go all right let me zoom out and I'm going to move everything

over okay um so the way we're going to keep track of the exclusion columns is like I said through an array um so if we have

four r four four columns we are going to have four spots here 1 2 3 four and then the

number uh here will it will be one I believe because we'll have the zero and then when we go to 32 oh this will be actually two when we

call it um you know I I need to move this down one more time so we have one when we call the the determinant function the first

time that'll be zero then we'll have a Z and a one then a 0 1 2 when we call it the here there are

three skip columns and then when we get the last element we have four skip columns 0 1 2 3 and

then we have four now now when we go back to determinant 32 and call determinant 44 we're going to have to remove this last element or not remove

it but we're going to have to update it um because we don't want to skip the third column in this last method and all we can all we actually have to do is just decrease the number of skip columns by one because if we just want to read

the first three elements we don't have to we don't really care what the last element is we can just leave it as is because the only thing that we care about is that the first three elements stay the same so when we call

determinant 44 it will be 1 0 1 2 3 at the beginning but then we will replace the three at the end with four because the number of skip calls going into this

method is three um and at index 3 it was three but now we're making it four I'm stumbling over my words but or I wasn't stumbling but I hope that made some

muchat sense this this will actually help more um if we do determinant um now

[Music] 33 this is going to equal so determinant 33 is we're essentially

taking um we're in this Matrix here how do I what is the here let's so we essentially by the time we get back to

to determinant 21 after these calls have finished or back to an array that has 0124 but the number number of skip

columns is two again because we subtracted it and after determinate 32 it's subtracted back to two so now when we call determinate

33 we have now 0o 1 and then three is the third column and then we now three skip columns again and this will expand the same

way um but if now if we go back to calling determinant 22 once again when we call this we have the same array that we finished

determinate 33 or 34 with um but this time we only start with we only care about uh the zero at the beginning that was called that we

started with the initial call so there's one skip column and then now that we call it with 2 two we insert the two into the col into the skip column list

and we have two skip columns now so this is like a stack like I said um but yeah so that that's pretty much how we're going to iterate through this and once again these blank elements are not

really blank the entire time we don't we just don't care what they say um so for example when we call determinant 33 there will be a four in that last spot

but we only care about the first three elements which is denoted by the number of skip columns um which tells us okay we only care about the first three elements

all right back to the code so this is just inserting that that current column into there um and then if this is just going

to be a the initial call so if row is equal to zero just row Plus+ you know actually I'm going to remove that and you know what I will change the call in

determinant in the determinant method to be expand across Row one this time because we'll be expanding across Row one all

right now we'll do the base case um if row is equal to m. rows that

means that we're on the last row so we just want to return single element we're going to have an unsigned int C is equal to m. calls so essentially we're going

to m. calls so essentially we're going to go from from the right side to the left side to to find which of the the

the First Column that is not excluded so unsigned in C is equal to M calls um yep and then so we're going to find

the last column not in the exclusion list so if the D reference of number skip calls does not equal zero there are skip columns to look through and then we

also want to say we we want to avoid an unnecessary check so if skip calls at the D reference of number of skip calls

minus one so the last element or the previous element um is equal does not equal zero then we have have a valid

column to check actually um so while contains uint this is just the function from the C mathematics. we're going to pass in skip

mathematics. we're going to pass in skip calls uh the number Valance will be the de reference of number skip calls and then the target will be C and while that's true we're going to say C minus

minus so we will go from the right to the left um to figure out which is which of the which column is not contained um once again this check here

is just because if we had a 1ex one array uh there would be a zero in the skip column list but we wouldn't want to check that um just because it's it's it's a useless

check it's just another function and call so we can just avoid that by uh just not calling the function and then outside of both if statements um but still inside the base case if statement

we're going to say return uh m. elements

at row minus one because we're working with array indes not right now not Matrix indices and then C minus one all right after the base case we're

going to have some placeholders float return is equal to 0.0 float and then Char co-actor sign is equal to negative 1 this is pretty much

or is equal to one sorry and this is similar to uh oh this is similar to what we had um in the in the previous

implementation and then once again we're going to co-actor expand um so for unsigned int C is equal to 1 C

is less than or equal to m. calls

C++ we're going to skip the excluded columns so if contains uh uint skip

calls the dfference of number of skip calls and then for the Target we want to determine if the current column is excluded then just

continue and then outside of the if statement we're going to have a result uh Place alter float res is equal to 0.0

float uh if M do elements at row minus one at C minus one does not equal 0.0 floats this is

because if we if the element is 0.0 float we don't want to we don't really care we if we multiply it will just get to zero so we're just going to avoid um

calling them recursively uh so do the recursive call if it's a if it's a value not if it's nonzero and just say re is

equal to co-actor sign times m. elements

the element so row minus one C minus one and then that times the determinant exclusion um passing in the matx

this we're going to go to the next row um the current column to skip in the recursive call would be this column then we'll just pass in skip calls and the

number of skip calls because remember we are going to keep track of these um we're going to keep track of them through the recursive calls um and then outside of that if

statement we just uh say R plus equals res and then we will say co-actor sign is equal to negative co-actor sign okay um so now to remove the

current column from the list after we've expanded we want to remove the current column from the list and all we can say there is just the D reference of number

skip calls minus minus and once again make sure that the D reference is in parentheses and then the minus minus is outside of the

parentheses and then um return rent so this this uh decrement here all it does it just tells the compiler that

we don't care about that last or the the that element anymore and we can overwrite it whenever um so yeah that's all that

is now we can go into main. C and we'll actually test this by printing out the the uh exclusion column or the exclusion list uh every time so I will print F

here um percent D percent [Music] D um percent

D yeah and then I'll print out row call and then D reference of number skip calls and then print you to write pass

in skip calls and then the this is not necessary if if you but this is just for demonstration purposes and then the number of skip

calls all right if we go into main.c let's get a nice 5x5 um

main.c let's get a nice 5x5 um determinant um okay there we go

nice okay um so I will create a matrix here mat m is equal to Matrix five rows five columns and then for the

arguments uh three 0 03 0 -3

0 -2 0 0 01 0 03 this is this is going to be an easy

Matrix just because there's so many zeros and then 0 -1 2 0 and 1 so we'll print out the Matrix and then um we will print out the

determinant uh passing in a reference to M all right so CD test run um that is not right

did it not it didn't like something8 is that right hey it worked um but yeah so you see how many how like the number of zeros here just

obliterated the number of calls um so we didn't need many calls here um but you see the initial call will give us just an array with zero in it um and then

we'll have the 01 then the 013 but you see how this is progressing in order um and then it it drops back um let me actually I I want to find a better

example because this isn't really too helpful no same thing um I'll do this

one oh you can't even see it God damn it okay um one two three four

5 4 619

8 12 10 2 7

0 4 6 1 9 8 and then 1 5

2 4 3 now if we run this um that is definitely not right

that seems more right but why was it screwing up give me one sec just going to fill my water okay that looks or you know let me put

this in my calculator just to see what the actual answer is it's 324 looks right second determinant 5x five oops

oops it is zero oh I guess this is God damn it you gave us a [ __ ] ass [ __ ] thing come on

buddy just give me a better array please what exam did I use an ex oh I use a 4x4 up here so that might be better just use a 4x4 cuz I actually

have a 4x4 that works so let me just try this out four and four 1 three God this is

tedious one 4 3 9 55 6

21 1 12 4 2 3 God damn it why

is I'm getting different results this is definitely this definitely has something to do with memory do I have like a leak or something or

um you know let me actually do something here in matrix. C I will initialize the values for the

array um so I'll skip the initializing array to putting that in the determinant function and then I will have a float R

is equal to this and then in determinant exclusion I will pass in skip calls and number of skip calls

all right let me see if this works now I mean the stack seems to be going right son of a [ __ ] oh and then I didn't return

anything then I also can go free skip calls 27 is that I don't think that's right it's not right because I'm just getting

the same [ __ ] errors um [ __ ]

[ __ ] I mean I guess we can just look through the list though um where is this so we call determinant M which is

determinant 1 0 where we have the list is just zero then 0 1 012 01 2 3 0 oh

they're that's not right oh I get I know why now because it's doing something with [ __ ] it's getting five elements but

that's you know maybe I should just have M calls plus one just to be safe but it shouldn't be doing that 27 no that didn't fix

it okay so I guess keep the M calls that that's number should be the same um

but let me debug and see when it's returning an element here I do want to see that so debug um break matrix. C line

1028 God damn Run Okay so we're 43 the 0123 that's right and we're calling it at 43

good um so step yep good okay yeah this isn't right why is why is it going 44 oh that's not right all right I'm going to have a

break point in and I'll say if row is equal to m. rows minus

one quit debug um break matrix.

c1015 run no I don't want 1019 break matrix.

c115 continue what the [ __ ] okay so it's just infinitely adding elements to the [ __ ] list but why what the

heck all right you know let me let me just walk through this we will break at line 19 run all right step

in one zero good all right number of skip calls should be uh just a zero so print skip calls at zero good

okay um step into here we're going 21 which is the next call good oops [ __ ] back into

two1 good so we're skipping the First Column good then we don't want to skip the second

one step in there 32 is the next call good next

next 012 that is is right good skipping columns one and two this time step in so

43 we should just be returning uh the elements step okay so we're going in the if statement that's good then unsigned in

C okay so it does not contain the fourth so we're going to print m. elements

or just print row minus or yeah row print C all right so 44 perfect then step step [ __ ] God

damn step in we're calling determinant 44 now oh no stepped into the function by accident

whoa whoa whoa whoaa why is it skipping what the hell what why is it skipping should not be skipping that this is this doesn't look

right skip calls at number of skip calls is equal to column number of skip calls plus plus God damn it all right I will debug again this

time I'll break at um 1026 um so we're calling it 43 that is

the first good so while it does not contain we have a zero one

two three and then we should stop good return false continue step into the function number

of element is equal to five no that's not right oh okay all right yeah okay I I forgot the crucial thing I said it in my demo and I forgot

to do it but you need to reset or subtract one from the skip columns we do it over here but the thing is we don't do it over when we return down here um

so we're going to say if we're going to skip the or subtract the skip columns after the Y Loop um so what happen what was happening was it

was returning over here properly at the end of the method after doing the expansion and subtracting one but when we returned the single element we didn't

actually decrement the skip columns so now if we run this we should get the proper answer 32 which is

Perfecto and there's no memory [ __ ] um and you can we can verify that this all works

um you have the one Zer the zero 0 1 012 012 3 012 4 and then it pops the four and then

replaces the two with a three or pops the two and then ads a three um keeps going 0 134 blah blah blah blah blah and then we

get to determinant 22 which is over why am I not seeing it 2 three should be here 21 22 here we go let we

get to determinate 22 and we call a z or we pass in 02 okay yeah so that was good wonderful error um all right so yeah that was kind

of the main thing that I wanted to talk about um there was another method but it it would take a while to explain it and we've already been live for just about

an hour and it's not I I'll put it in the code but um it just has to do with uh doing a modified row Echelon form of the uh of the Matrix which isn't too

impressive but um there's a lot of conceptual stuff there but yeah so this is a more efficient recursive method rather than

then cutting out all of these columns and [ __ ] or and making all these copies

um so uh yeah it's pretty much it I hope you guys learned something this was I I actually almost creamed my pants last night when I when I figured this out um

because it was so cool I was so proud of myself um but uh yeah so sounds uh pretty

good um all I got to go do some work so uh I'll see you guys maybe on the weekend I doubt it though because I I think I'm pretty or maybe Saturday might

be busy though um but until the next stream hope you guys enjoy yourselves protect yourselves eat well drink well

um and uh yeah keep yourself safe and uh I'll see you then for