MathGroup Archive 1995

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: RealDigits

  • To: mathgroup at christensen.cybernetics.net
  • Subject: [mg1862] Re: [mg1741] RealDigits
  • From: Count Dracula <lk3a at kelvin.seas.virginia.edu>
  • Date: Wed, 9 Aug 1995 22:38:17 -0400
  • Organization: University of Virginia

(Dave Wagner) wagner at bullwinkle.cs.Colorado.EDU writes:

> For example, the following function checks a matrix
> to see if it is diagonal:

>    DiagonalQ[m_] :=
>	And @@ Flatten[ MapIndexed[ #1==0 || Equal @@ #2 &, m, {2} ]]

> Here's another one that checks for upper-triangularity:

>    UpperTriangularQ[m_] :=
>	And @@ Flatten[ MapIndexed[ #1==0 || LessEqual @@ #2 &, m, {2} ]]

These functions check every member of the matrix and the || forces another
condition check if the first equality check comes out false. For an n by n
matrix, the number of checks could be as high as 2 n^2.

If the purpose is to give an example of MapIndexed and write similar functions
for checking certain forms of matrices, the following functions also do this,
and they are more efficient:

  diagQ[m_?MatrixQ] /; SameQ @@ Dimensions[m] := 
      With[{n = Length[m]},
             Flatten[ MapIndexed[Drop, m] ] == Table[0, {n(n - 1)}]
          ]

  utriQ[m_?MatrixQ] /; SameQ @@ Dimensions[m]  := 
      With[{n = Length[m]},
             Flatten[ MapIndexed[Take[#1, First[#2] - 1]&, m] ] == Table[0, {n(n-1)/2}]
          ]


Test run for Timing checks:

  mat = Table[1, {120}, {120}];

  test := {Timing[DiagonalQ[mat]], Timing[diagQ[mat]]}

  test2 := {Timing[UpperTriangularQ[mat]], Timing[utriQ[mat]]}


In[7]:= test

Out[7]= {{4.3 Second, False}, {0.18 Second, False}}

In[8]:= test2

Out[8]= {{4.48 Second, False}, {0.17 Second, False}}

(A faster function due to Roman Maeder for diagonal matrices is
            dQ[m_?MatrixQ] /; SameQ @@ Dimensions[m] :=
                m == DiagonalMatrix[Transpose[m, {1, 1}]]
)

> Doubtless you could also come up with more efficient
> (though not necessarily more understandable) functions for checking
> the other conditions that I mentioned, such as lower- and
> upper-triangular, etc.  But MapIndexed provides a unifying framework
> for all of these, and in that sense it's "perfect".

The functions diagQ, utriQ ( and of course dQ ) are, in fact, more easily
understandable.  MapIndexed is usable, but the particular examples of it in
DiagonalQ and UpperTriangularQ create plodding Mathematica functions,
because they check too many individual conditions. The functions diagQ,
utriQ can be a 20 to 25 times faster, and all they do is check equality
conditions on larger lists and eliminate the entirely superfluous checks on
the equality of row and column indices.

> I stand by the statement above,
> which is that MapIndexed provides an easy-to-understand way to solve an
> entire class of problems in an essentially similar way.

The functions (DiagonalQ and UpperTriangularQ) supplied to support this
statement are examples of how not to program in Mathematica.


-- 
___________________________________________________________________________________
Levent Kitis           lk3a at cars.mech.virginia.edu    lk3a at kelvin.seas.virginia.edu
University of Virginia Department of Mechanical, Aerospace, and Nuclear Engineering  


  • Prev by Date: Comparison of Mma animations on various machines
  • Next by Date: Re: RealDigits
  • Previous by thread: Re: RealDigits
  • Next by thread: Re: RealDigits