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>
- Creating a symmetric matrix