Row or column equal 0
Author
Anyone know a good logic test, fast algorithm, to detect if a column or a row in a nxn matrix is equal to 0 ?
If its a square matrix then the determinant will be equal to zero (within an error value if using floats or doubles).
If its non-square you''ll probably have to look at all the rows (or columns if num columns < num rows ).
"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley
If its non-square you''ll probably have to look at all the rows (or columns if num columns < num rows ).
"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley
quote:
If its a square matrix then the determinant will be equal to zero
True, but there are matrices with non-zero rows/columns whose determinants are equal to zero. Consider for example:
[1 2]
[2 4]
[edited by - Muzzafarath on March 22, 2004 11:13:23 AM]
Thats true but the matrix is still degenerate in that case.
Just loop through the rows or columns until you find a non-zero value. There might be a better algorithm, its more like a string search than specifically matrix and maths.
You could work out the determinant before looking at the values, of course.
What is it for anyway?
Just loop through the rows or columns until you find a non-zero value. There might be a better algorithm, its more like a string search than specifically matrix and maths.
You could work out the determinant before looking at the values, of course.
What is it for anyway?
You could keep a list of rows and columns which can potentially be filled with 0, and read all elements of the matrix, in order, which belong to a potentially-0 column or row. If it''s a 0, then move on, if it''s not then the corresponding row and column aren''t potentially-0 anymore, and move on. Once you reach the end, any potentially-0 row or column is an actual 0 row or column, and the others aren''t.
Variation : read each potentially-0 row until it turns non-potentially-0, same for columns.
Paradigm shifter : a brute-force search on that problem would be O(n²), and you can achieve even less with a better algorithm, computing the determinant of an nxn matrix is O(n!). The determinant method is therefore a bad idea.
Variation : read each potentially-0 row until it turns non-potentially-0, same for columns.
Paradigm shifter : a brute-force search on that problem would be O(n²), and you can achieve even less with a better algorithm, computing the determinant of an nxn matrix is O(n!). The determinant method is therefore a bad idea.
Victor Nicollet, INT13 game programmer 
what I want is to check if the determinant of a matrix is 0 before to do the determinant, that maybe can avoid some calculus, but I don''t know if the check woll eat more time than do the determinant anyway, although a row or col = 0.
If the question is to determine if a row or column has only zeroes in it, I would suggest, for each column and each row, adding the absolute values together and if the sum is zero, then all elements are zero.
That''s (r x c)^2 additions.
To determine if the matrix can be manipulated so a column or a row can be zeroised, you need to evaluate the determinant. If it is zero, then a row or a column can be manipulated to make it zero, if one isn''t already so.
Stevie
Don''t follow me, I''m lost.
That''s (r x c)^2 additions.
To determine if the matrix can be manipulated so a column or a row can be zeroised, you need to evaluate the determinant. If it is zero, then a row or a column can be manipulated to make it zero, if one isn''t already so.
Stevie
Don''t follow me, I''m lost.
You might be able to do it via this pseudocode:
similar for columns. Then it'll run at worst 2n2 times if its a matrix like:
0001
0001
0001
0000
Scout
All polynomials are funny - some to a higher degree.
Furthermore, polynomials of degree zero are constantly funny.
[edited by - MrScout on March 22, 2004 4:07:20 PM]
while (x < n){ while (y < n) { if (M[x][y] != 0) { x++; y=0; } } if (y == n) return ZERO_ROW;}similar for columns. Then it'll run at worst 2n2 times if its a matrix like:
0001
0001
0001
0000
Scout
All polynomials are funny - some to a higher degree.
Furthermore, polynomials of degree zero are constantly funny.
[edited by - MrScout on March 22, 2004 4:07:20 PM]
I''m afraid, there isn''t much optimizations to be done, if you already know which column that you want to check, and you don''t want to check all of the columns at once. An if test is as fast as it''s going to get.
Why do you need that? I find it hard to imagine a situation where this operation is a bottleneck; it should be quite fast.
Why do you need that? I find it hard to imagine a situation where this operation is a bottleneck; it should be quite fast.
There is one small optimization that can be done. Try a bitwise or of all the elements of the row/column, and check that against 0. This way you never need to load any of the elements into the floating point coprocessor and you have reduced conditional branching compared to doing a test against each element one at a time.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
