Optimising subdiagonal shift matrix generation time
ClearAll[tminus1, tminus2, tminus3, tminus4, tminus5]
tminus1[n_] := ArrayPad[IdentityMatrix[n - 1, SparseArray], {{1, 0}, {0, 1}}]
tminus2[n_] := DiagonalMatrix[ConstantArray[1, n-1], -1]
tminus3[n_] := SparseArray[{i_, j_} /; j == (i - 1) -> 1, {n, n}]
tminus4[n_] := IdentityMatrix[n+1, SparseArray][[;;-2, 2;;]]
tminus5[n_] := Drop[IdentityMatrix[n+1, SparseArray], {-1}, {1}]
tminus1[5] // MatrixForm // TeXForm
$\left( \begin{array}{ccccc} 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ \end{array} \right)$
Timings: Including tminus0
(from OP) , tminus6
(from Roman's answer) and tminus7
(from Shadowray's answer):
tminus0[n_] := Table[If[i == j + 1, 1, 0], {i, 1, n}, {j, 1, n}]
tminus6[n_] := SparseArray[Band[{2, 1}] -> 1, {n, n}]
tminus7[n_] := DiagonalMatrix[ConstantArray[1, n-1, SparseArray], -1]
funcs ={"tminus1 - arraypad", "tminus3 - sparsearray", "tminus4 - part",
"tminus5 - drop","tminus6 - sparsearray-band", "tminus7 - diagonalmatrix-sparseArray"};
Version/OS:
$Version (on Wolfram Cloud)
12.0.0 for Linux x86 (64-bit) (April 7, 2019)
n = 100;
t0 = First[AbsoluteTiming[r0 = tminus0[n];]];
t1 = First[AbsoluteTiming[r1 = tminus1[n];]];
t2 = First[AbsoluteTiming[r2 = tminus2[n];]];
t3 = First[AbsoluteTiming[r3 = tminus3[n];]];
t4 = First[AbsoluteTiming[r4 = tminus4[n];]];
t5 = First[AbsoluteTiming[r5 = tminus5[n];]];
t6 = First[AbsoluteTiming[r6 = tminus6[n];]];
t7 = First[AbsoluteTiming[r7 = tminus7[n];]];
Equal[r0, r1, r2, r3, r4, r5, r6, r7]
True
timings = {t0, t1, t2, t3, t4, t5, t6, t7};
Column[{"n = 100",
Grid[Prepend[SortBy[Transpose[{funcs, timings}], Last],
{"function", "timing"}], Dividers -> All, Alignment -> "."]}]
I exclude tminus0
and tminus2
(due limited cloud credit) for n = 10000
and for n = 100000
:
tminus[n_Integer /; n >= 2] := SparseArray[Band[{2, 1}] -> 1, {n, n}]
Since your matrix is large and has very few nonzero elements it is much more efficient to create and store it as a SparseArray
. In addition many matrix operations are optimized to work faster with SparseArrays.
In order to efficiently generate sparse subdiagonal matrix you can use following function:
tminus7[n_] := DiagonalMatrix[ConstantArray[1, n-1, SparseArray], -1]
Both DiagonalMatrix
and ConstantArray
can output SparseArrays,
but you have to explicitly specify SparseArray
option, otherwise a large non-sparse array will be generated at intermediate step and the performance will be much lower (as shown by tminus2
function in kglr's answer).
Let's compare this method with the fastest function from kglr's answer (tminus1
):
tminus1[n_] := ArrayPad[IdentityMatrix[n - 1, SparseArray], {{1, 0}, {0, 1}}]
n=10000;
t1=First[RepeatedTiming[r1=tminus1[n];]];
t7=First[RepeatedTiming[r7=tminus7[n];]];
Equal[r1,r7]
True
{t1,t7}
{0.000072, 0.000025}
Thus, for large matrices this function is about 3 times faster than the fastest function (tminus1
) from the top answer.