11
$\begingroup$

I am considering identities involving t[a, b, c, d, ...], where number of indices is fixed. t has the cyclic property so that t[3, 4, 1, 2] is equal to t[1, 2, 3, 4].

When $k=4$, all possible elements are generated by

basis = (# /. {List -> t}) & /@ Permutations[Range[4]];
basis = basis /. {t[a___, 1, b___] -> t[1, b, a]} // Union

Here comes the output:

{t[1, 2, 3, 4], t[1, 2, 4, 3], t[1, 3, 2, 4], t[1, 3, 4, 2], t[1, 4, 2, 3], t[1, 4, 3, 2]}

I want to convert expressions like t[1, 2, 3, 4] + t[1, 3, 2, 4] - t[1, 4, 3, 2] into a coefficient matrix to do some linear algebra. I tried the following code:

identity = {t[1, 2, 3, 4] + t[1, 3, 2, 4] - t[1, 4, 3, 2], 
  t[1, 2, 4, 3] + t[1, 3, 2, 4], 
  t[1, 3, 4, 2] - t[1, 2, 3, 4] - t[1, 4, 2, 3]};

coeffmatrix = Coefficient[identity, #] & /@ basis // Transpose

The output is

{{1, 0, 1, 0, 0, -1}, {0, 1, 1, 0, 0, 0}, {-1, 0, 0, 1, -1, 0}}.

Efficiency does not matter for this small example. However, when I increase number of indices and identities, getting coeffmatrix becomes very slow and spends a huge amount of memory. For the real case, t has 10 indices and the size of coeffmatrix is approximately $362880 \times 362880$.

Here comes my question: Coefficients are always restricted to {-1, 0, 1} for some reasons. Would this fact probably help me to boost up the performance? Could anyone give me a suggestion for better efficiency?

$\endgroup$
6
  • $\begingroup$ Would using a SparseArray help? $\endgroup$ Apr 10, 2013 at 0:58
  • $\begingroup$ @TobiasHagge I am not familiar with SparseArray. What is the benefit to use SparseArray? $\endgroup$
    – Joonho Kim
    Apr 10, 2013 at 1:06
  • $\begingroup$ more efficient storage and faster computations on matrices for which most of the coefficients are zero. $\endgroup$ Apr 10, 2013 at 4:56
  • $\begingroup$ @TobiasHagge Is it possible to calculate the matrix rank directly from SparseArray? $\endgroup$
    – Joonho Kim
    Apr 10, 2013 at 5:47
  • $\begingroup$ I haven't used sparse arrays much, but my understanding is that most of mathematica's linear algebra functions are implemented to transparently work with them. CoefficientArrays, by the way, produces a SparseArray, so if you want to test performance you can compute the rank using the matrices computed by both your algorithm and Mr. Wizard's, and see which is faster. $\endgroup$ Apr 10, 2013 at 15:29

2 Answers 2

8
$\begingroup$

Is this faster?

CoefficientArrays[identity, basis][[2]] // MatrixForm

$\left( \begin{array}{cccccc} 1 & 0 & 1 & 0 & 0 & -1 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ -1 & 0 & 0 & 1 & -1 & 0 \end{array} \right) $


Responding to Jens' elegant answer it should be noted that performance of CoefficientArrays is better optimized for this task as one would hope.

basis = (# /. {List -> t}) & /@ Permutations[Range[8]];
basis = basis /. {t[a___, 1, b___] -> t[1, b, a]} // Union;

size = {5000, 30};
identity = Total[RandomInteger[{-1, 1}, size]*RandomChoice[basis, size], {2}];

(r1 = CoefficientArrays[identity, basis][[2]];) // RepeatedTiming // First
(r2 = D[identity, {basis}];)                    // RepeatedTiming // First

r1 == r2
0.0517

0.43

True

In this example the difference in memory consumption is far more significant:

ByteCount /@ {r1, r2}
Divide @@ % // N

{1639856, 608080968}

0.00269677
$\endgroup$
3
  • $\begingroup$ Amazing! It's about 100 times faster than before. Can we do the same linear algebra with SparseArray? $\endgroup$
    – Joonho Kim
    Apr 10, 2013 at 1:21
  • $\begingroup$ @JoonhoKim post a new question with a specific example and I'll try to answer that. $\endgroup$
    – Mr.Wizard
    Apr 10, 2013 at 8:42
  • $\begingroup$ Indeed, I noticed similar timing differences with the original example by just repeating it many times. $\endgroup$
    – Jens
    May 28, 2015 at 1:12
5
$\begingroup$

To convert a list of linear expressions to a matrix containing the coefficients the following is easier to write than CoefficientArrays, but seems to be a little slower:

D[identity, {basis}]

$$\left( \begin{array}{cccccc} 1 & 0 & 1 & 0 & 0 & -1 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ -1 & 0 & 0 & 1 & -1 & 0 \\ \end{array} \right)$$

What I did here is to use the fact that for a linear map the matrix of coefficients is identical to the Jacobian. The latter is what I calculate.

$\endgroup$
4
  • $\begingroup$ This is beautiful but in my testing it is slower than CoefficientArrays. I guess you just noticed that too. It also produces a dense array that could take up quite a bit of memory in some cases. $\endgroup$
    – Mr.Wizard
    May 28, 2015 at 0:51
  • 1
    $\begingroup$ @Mr.Wizard Yes, my initial timing included the duration of the keystrokes... $\endgroup$
    – Jens
    May 28, 2015 at 0:53
  • 1
    $\begingroup$ A metric I use myself if you haven't guessed. :D $\endgroup$
    – Mr.Wizard
    May 28, 2015 at 0:55
  • $\begingroup$ You already have my vote but I thought it worthwhile to note the performance caveats so I added an example to my answer. If you feel it is an unfair example please let me know; I chose it without much consideration. $\endgroup$
    – Mr.Wizard
    May 28, 2015 at 1:03

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.