5
$\begingroup$

Suppose I have

f[x_] := SparseArray[{someRules}, {m, m}];
g[x_] := MatrixPower[f[x], k];

Would it be possible to evaluate only the $n$-th column ($n\neq m$) of g without evaluating the whole thing?

Would a simple a = g[x'][[n]] work? Or should I define f and g differently?

EDIT: I just noticed I wrote the above expression for a row, not a column, so the correct expression would be a = g[x'][[All, 1]]. Just a defect of form, of course; the problem still is the same.

$\endgroup$
12
  • 2
    $\begingroup$ a = g[x'][[n]] certainly will not work. It is an interesting question and a difficult problem. I'm inclined to say it is not possible, unless your columns all happen to be linearly independent, but hopefully I will be proved wrong. $\endgroup$ Commented Sep 23, 2015 at 17:10
  • 1
    $\begingroup$ @PatrickStevens to form a matrix power requires a matrix decomposition (e.g. SVD), does it not? And this operation depends on the whole matrix, not just one column. I interpret the question as asking how we can avoid doing calculations that affect only values not lying in this column. $\endgroup$ Commented Sep 23, 2015 at 17:13
  • 1
    $\begingroup$ Never use N as a variable, since it is a Mathematica function (give numerical value). It is also good practice to avoid all upper-case letters for variables, such as your K. Also do not use upper-case for named terms, such as Rules, since it may conflict with the thousands of Mathematica function names (such as the close Rule). Don't even do it as an "example," as others will cut-and-paste your code. Get into good coding habits! You could very very easily use myRules, n, and k here, no matter how complicated your own terms were. $\endgroup$ Commented Sep 23, 2015 at 17:18
  • 1
    $\begingroup$ Have you tried just working out the indexed form of the product of a matrix K times? That seems like the most straightforward way. Wikipedia even has the sums worked out on the Matrix Multiplication page, you'd just need to translate it to MMA. $\endgroup$
    – N.J.Evans
    Commented Sep 23, 2015 at 17:30
  • 2
    $\begingroup$ Based on some simple testing the general result depends on the entire f matrix, so there is no way around that. (Of course if there is some specific structure to the sparse array that might change things ) $\endgroup$
    – george2079
    Commented Sep 23, 2015 at 18:40

1 Answer 1

1
$\begingroup$

The documentation for MatrixPower[] indicates that you can take the action of a matrix power on a given vector. In particular, to get a single column of a matrix power, you thus need the action of the matrix power on an appropriate unit vector.

For instance,

n = 6;
mat = SparseArray[{{j_, k_} /; j + k == n + 1 :> 1, {k_, k_} :> 1}, {n, n}];

m = 4; (* power *) k = 3; (* column *)
MatrixPower[mat, m, UnitVector[n, k]]
   {0, 0, 8, 8, 0, 0}

mp = MatrixPower[mat, m];
mp[[All, k]]
   {0, 0, 8, 8, 0, 0}

MatrixExp[] also admits an "action" form.

$\endgroup$
5
  • $\begingroup$ I didn't know about this. Does this speed up the process? $\endgroup$
    – Enzo
    Commented Oct 8, 2015 at 11:13
  • $\begingroup$ Assuming that they implemented it properly under the hood, yes. Actions of matrix functions are an active area of research, it should be said. $\endgroup$ Commented Oct 8, 2015 at 11:29
  • $\begingroup$ Alright. What if now, instead of MatrixPower, I wanted to do multiplications between matrices? They all have the same structure. For example, I'd like to do a := Table[{RandomChoice[{i, j}], ... , RandomChoice[{k, l}]}, {n}] (where a is set delayed) so I'd want the k-th column of b=a.a.a ... .a Is this possible, or should I just take the column, now? $\endgroup$
    – Enzo
    Commented Oct 11, 2015 at 17:01
  • $\begingroup$ I don't know if there's a more efficient way than just multiplying the matrices in sequence to a unit vector. $\endgroup$ Commented Oct 11, 2015 at 17:28
  • $\begingroup$ 31 hours reduced to just 40 minutes... I'd say that's an improvement! Thank you so much. $\endgroup$
    – Enzo
    Commented Oct 16, 2015 at 9:46

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.