Re: Creating a symmetric matrix

*To*: mathgroup at smc.vnet.net*Subject*: [mg46888] Re: [mg46853] Creating a symmetric matrix*From*: "Sseziwa Mukasa,,(978) 536-2359" <mukasa at jeol.com>*Date*: Fri, 12 Mar 2004 23:39:57 -0500 (EST)*References*: <200403110850.DAA13986@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

On Mar 11, 2004, at 3:50 AM, Mark Coleman wrote: > Greetings, > > How can I efficiently build a symmetric matrix from an upper triangular > one, i.e., extract the upper triangular elements and insert them into > the lower triangle in such a way as to make the resulting square matrix > symmetric? > You need to define what you mean by efficient. As Jens, Paul and Oleksandr have demonstrated, there are some very simple expressions to build a symmetric matrix from an upper triangular matrix. They all scale as the square of the matrix dimension. Timing tests on my machine, a dual 1GHZ G4 PowerMac, indicate Paul and Oleksandr's solutions are about equally as fast (2.5 vs 3s for a 2000x2000 array), and Jen's takes 70s for the same size array. However all those solutions build a transposed copy of the array as an intermediate step, which for a large array is not memory efficient. Actually, the most memory efficient storage method for a triangular array is as a list of lists each of which corresponds to the nonzero elements of a row ie. {{x,x,x,x},{x,x,x},{x,x},{x}} for a 4x4 upper triangular matrix. I know about SparseArrays, I'll discuss them later. If you store your matrix in this form, the following function will generate the symmetric version: symmetricfromuppertriangular[a_] := MapIndexed[With[{r = #2[[1]]}, If[r > 1, \ Join[a[[Sequence @@ #]] & /@ Transpose[{Range[r - 1], Range[r, 2, -1]}], #], #]] &, a] This is about as time efficient as Jen's solution. I noticed however that for a lower triangular matrix stored in memory efficient format ie. {{x},{x,x,},{x,x,x},...} the following function can generate a symmetric matrix: symmetricfromlowertriangular[a_] := With[{l = Length[a]}, MapIndexed[With[{r = #2[[1]]}, If[r < l, Join[#, a[[Range[ r + 1, l], r]]], #]] &, a]] and it is the fastest implementation I've found at 1.4s for the 2000x2000 case. Since the lower triangular form is equivalent to column major order storage of an upper triangular matrix the same function can be applied. The lower triangular form also works on the array stored explicitly as {{x,0,0},{x,x,0},{x,x,x}} so you could apply it to the transposed version of an upper triangular matrix. Given that the difference between symmetricfromlowertriangular and symmetricfromuppertriangular stem from computing the indices into the structure I though I'd try using sparse arrays which are supposed to work with Part efficiently. However Join doesn't seem to work with them. The following function: sparsesymmetrizefromupper[a_] := With[{d = Length[ a]}, Join[Normal[a[[1, All]]], Prepend[Normal[a[[2, Range[ 2, d]]]], a[[1, 2]]], Table[Join[Normal[a[[Range[r - 1], r]]], Normal[a[[r, Range[r, d]]]]], {r, 2, d - 1}], Append[a[[Range[ d - 1], d]], a[[d, d]]]]] crashed the kernel on my machine when fed a sparse array. The odd structure of the expression is because it also crashed when attempting to evaluate a[[i,{j}]] when a is a SparseArray. Regards, Ssezi

**References**:**Creating a symmetric matrix***From:*Mark Coleman <mark@markscoleman.com>