Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2004
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2004

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: Integrate vs NIntegrate
  • Next by Date: Re: Excessive Mathematica memory use, revisited.
  • Previous by thread: Re: Creating a symmetric matrix
  • Next by thread: Re: Creating a symmetric matrix