I found this question quite interesting, so I thought I would collect the answers contributed in comments for future reference and to have the question appear as answered in search. I generated a slightly bigger matrix to play with, and minimally modified the code to render it independent of the size of the matrix. I also compared timings of each method to have a homogeneous set at least on my system (MMA 10.2 on Win7-64bit).
SeedRandom[23]
a = (# + Transpose[#])& [RandomReal[{-1, 1}, {5000, 5000}]];
If the matrix is symmetric, as was the case in the OP and in the example above, then taking advantage of its structure yields the fastest solution so far, already originally proposed by arax in the question:
(Total[a, 2] - Tr[a])/2 // RepeatedTiming
(* Out: {0.025, -1769.6} *)
In the general case of a non-symmetrical matrix, however, the above solution of course wouldn't work. The Toad proposed a very compact solution using UpperTriangularize. Timings show that Flatten
is bad for speed; much more expedient is to use a levelspec option for Total.
Total@Flatten@UpperTriangularize[a, 1] // RepeatedTiming
Flatten@a; // RepeatedTiming
Total[UpperTriangularize[a, 1], 2] // RepeatedTiming
(* Out:
{0.338, -1769.6}
{0.20, Null}
{0.134, -1769.6}
*)
Similarly one could use LowerTriangularize to get the sum of the lower triangular portion of a non-symmetric matrix: Total[LowerTriangularize[a, -1], 2]
.
Kale then proposed a faster approach based on explicit part extraction. The version proposed in the comment actually sums the lower triangular members of the original matrix, which made no difference in the case of a symmetric matrix, but of course would matter in the general case. Two versions are presented here, for upper and lower triangles (which also required a slight adjustment to the Range
used):
(* Upper triangular version *)
Total[a[[#, # + 1 ;; -1]] & /@ Range[1, Length[a]], 2] // RepeatedTiming
(* Out: {0.0940, -1769.6} *)
(* Lower triangular version *)
Total[a[[#, 1 ;; # - 1]] & /@ Range[1, Length[a]], 2] // RepeatedTiming
(* Out: {0.104, -1769.6} *)
Although faster in this case, the intermediate list of parts generated in this approach is ragged, which may lead to unpacking of packed arrays (see e.g. Leonid's discussion on the topic).
N.J. Evans proposed a simple modification to Kale's solution that yields a significantly faster method, by simply applying Total
twice in a row, rather than using a levelspec:
Total[Total@a[[#, # + 1 ;; -1]] & /@ Range[1, Length[a]]] // RepeatedTiming
(* Out: {0.04, -1769.6} *)
This works exceedingly well for the part-extraction approach, where it may have to do with the fact that the outer Total
is presented with the much simpler job of summing over a list, thanks to the inner Total
, which may also have had the advantage of quick mapping.
In support of this hypothesis is also the fact that the same approach does not yield faster results in the *Triangularize
approach.
Finally, the approach based on Sum
presented in the OP as a slow comparison is, indeed, very slow:
Sum[a[[i, j]], {i, 1, Length[a]}, {j, i + 1, Length[a]}] // RepeatedTiming
(* Out: {18.3, -1769.6} *)
Total@Flatten@UpperTriangularize[a, 1]
(orTotal[..., 2]
w/oFlatten
). Probably not as fast as theTotal - Tr
route, but easier to read perhaps. $\endgroup$Flatten
took half of the time in the first expression. Both are fast enough to sum a matrix the size of my available RAM. $\endgroup$Total[a[[#, ;; # - 1]] & /@ Range[2, 1000], 2] // AbsoluteTiming
isn't too bad. $\endgroup$