14
$\begingroup$

Today, I got to thinking about how to test that a matrix was upper-triangular. So I had a try at it.

Algorithm

$\quad \quad a_{ij}=0 $ Or $i \leq j$ $\Rightarrow$ $True$

My solution is

upperTriangularMatrixQ[mat_?MatrixQ] /; Equal @@ Dimensions@mat :=
  And @@ Flatten @ MapIndexed[#1 == 0 || LessEqual @@ #2 &, mat, {2}]

Performance testing

Sample data

testMat1 = UpperTriangularize@RandomInteger[{1, 100}, {1000, 1000}];
testMat2 = RandomInteger[{1, 100}, {1000, 1000}];

Test

upperTriangularMatrixQ@testMat1 // Timing
{3.151, True}
upperTriangularMatrixQ@testMat2 // Timing
{3.978, False}

My question

Can you come up with a better performing algorithm to solve this problem?

$\endgroup$
4
  • $\begingroup$ It looks like you are looping over all $i$ and $j$. You don't have to even check the cases where $i \ge j$ That is worth a factor $2$ $\endgroup$ Sep 19, 2014 at 4:06
  • $\begingroup$ @RossMillikan, when $i > j $, the value of $a_{ij}$ must be zero. $\endgroup$
    – xyz
    Sep 19, 2014 at 7:00
  • $\begingroup$ @RossMillikan, with help of Mr.Wizard, I know that diagonal do not need to be checked. $\endgroup$
    – xyz
    Sep 19, 2014 at 7:11
  • $\begingroup$ @Mr.Wizard, I am always learning new Mathematica knowledge from your answer. $\endgroup$
    – xyz
    Sep 19, 2014 at 13:49

3 Answers 3

9
$\begingroup$

You did not specify if this test should be optimized for the positive or negative case. If most of your matrices will fail the test it can be greatly beneficial to have an early exit behavior. For example if the lower left element in the matrix is not zero you can fail the matrix after a single element test! And even in the positive case the elements on or above the diagonal do not need to be checked.

Therefore I propose:

utmQ[m_?SquareMatrixQ] :=
  VectorQ[Range[Length@m - 1], m[[# + 1, ;; #]] == ConstantArray[0, #] &]

For earlier versions you can replace SquareMatrixQ with the original argument test and condition.

Timings:

Needs["GeneralUtilities`"]

false = RandomInteger[{-9, 9}, {15000, 15000}];
true = UpperTriangularize[false];

utmQ[false] // AccurateTiming
utmQ[true]  // AccurateTiming
0.000029297

0.195

mfvonh's method for comparison:

upperTriangularMatrixQ2[false] // AccurateTiming
upperTriangularMatrixQ2[true]  // AccurateTiming
0.705001

0.795001

So you see that my method is four times faster in the positive case, and potentially orders of magnitude faster in the negative case.

$\endgroup$
7
  • $\begingroup$ I forgot that diagonal do not need to be checked.+1 :-) $\endgroup$
    – xyz
    Sep 19, 2014 at 7:14
  • $\begingroup$ @Tangshutao Are you running Mathematica 10? $\endgroup$
    – Mr.Wizard
    Sep 19, 2014 at 7:20
  • $\begingroup$ ♦, No, just on V8.0.1 and I got used to use that version $\endgroup$
    – xyz
    Sep 19, 2014 at 7:29
  • $\begingroup$ Dear Mr.W, I think your solution :utmQv9[m_?MatrixQ] /; Equal @@ Dimensions[m] := Null === Do[ If[m[[i + 1, ;; i]] != ConstantArray[0, i], Return[1]], {i, Length@m - 1}] is faster then my algorithm. $\endgroup$
    – xyz
    Sep 19, 2014 at 7:31
  • $\begingroup$ @Tangshutao Okay. I simplified my answer as the same (body) code will work in both versions, but you will need to replace SquareMatrixQ with your original argument tests, e.g. start with: utmQ[m_?MatrixQ] /; Equal @@ Dimensions@m := $\endgroup$
    – Mr.Wizard
    Sep 19, 2014 at 7:31
12
$\begingroup$

Maybe

upperTriangularMatrixQ2[mat_?MatrixQ] /; Equal @@ Dimensions@mat := 
  UpperTriangularize@mat == mat;

test = RandomInteger[{1, 100}, {1000, 1000}];
upperTriangularMatrixQ@test // AbsoluteTiming

{2.126050, False}

upperTriangularMatrixQ2@test // AbsoluteTiming

{0.003277, False}

test2 = UpperTriangularize@test;
upperTriangularMatrixQ@test2 // AbsoluteTiming

{1.706272, True}

upperTriangularMatrixQ2@test2 // AbsoluteTiming

{0.004966, True}

$\endgroup$
3
  • $\begingroup$ Good idea!+1,Thanks. $\endgroup$
    – xyz
    Sep 19, 2014 at 3:03
  • 1
    $\begingroup$ I don't think it can be done any faster $\endgroup$ Sep 19, 2014 at 3:04
  • 1
    $\begingroup$ @belisarius Please see my answer. :D $\endgroup$
    – Mr.Wizard
    Sep 19, 2014 at 7:09
1
$\begingroup$

Since V 12.0 we have UpperTriangularMatrixQ:

testMat1 = UpperTriangularize @ RandomInteger[{1, 100}, {1000, 1000}];

testMat2 = RandomInteger[{1, 100}, {1000, 1000}];

UpperTriangularMatrixQ @ testMat1 // Timing

{0.000803, True}

UpperTriangularMatrixQ @ testMat2 // Timing

{0.000018, False}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.