next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
SVDComplexes :: SVDComplexes

SVDComplexes -- support for computing homology, ranks and SVD complexes, for a chain complex over the real numbers

Description

This package implements the algorithms in the paper "Singular value decomposition of complexes", by D. Brake, J. Hauenstein, F. Schreyer, A. Sommese, and M. Stillman, https://arxiv.org/abs/1804.09838.

Singular value decompositions of matrices are extremely useful in practice. In particular, an SVD can often reveal the rank (numeric rank) of a matrix.

In the above paper, we extend the notion of singular value decomposition from matrices over the reals or complexes to a complex of matrices over the reals or complexes.

For some applications, one obtains a complex over the (approximate) reals, and one would like to know what the ranks of the matrices are, and therefore the ranks of the homology groups. One way to do this would be to compute the SVD of each matrix separately, often revealing the desired ranks. This is less than satisfactory however, as it ignores the fact that this sequence is an approximation of a complex, i.e. each two consecutive matrices multiply to zero.

In this package, and the referenced paper, we give 2 algorithms for computing the SVD of a complex, and the resulting putative ranks of the matrices or ranks of the homology groups.

Here is an example of the usage. We construct a random chain complex whose homology modules have ranks 1, 4, 6, 5, and 1:

i1 : needsPackage "RandomComplexes"

o1 = RandomComplexes

o1 : Package
i2 : h = {1,4,6,5,1}

o2 = {1, 4, 6, 5, 1}

o2 : List
i3 : r = {1,3,3,4}

o3 = {1, 3, 3, 4}

o3 : List
i4 : C = randomChainComplex(h,r)

       2       8       12       12       5
o4 = ZZ  <-- ZZ  <-- ZZ   <-- ZZ   <-- ZZ
                                        
     0       1       2        3        4

o4 : ChainComplex
i5 : CQ = C ** QQ

       2       8       12       12       5
o5 = QQ  <-- QQ  <-- QQ   <-- QQ   <-- QQ
                                        
     0       1       2        3        4

o5 : ChainComplex
i6 : prune HH CQ

           1
o6 = 0 : QQ

           4
     1 : QQ

           6
     2 : QQ

           5
     3 : QQ

           1
     4 : QQ

o6 : GradedModule
i7 : CR = C ** RR_53

         2         8         12         12         5
o7 = RR    <-- RR    <-- RR     <-- RR     <-- RR
       53        53        53         53         53
                                                
     0         1         2          3          4

o7 : ChainComplex
i8 : (h,U) = SVDComplex CR

                            
o8 = (HashTable{0 => 1}, 0 :
                1 => 4      
                2 => 6      
                3 => 5
                4 => 1      
                         1 :
                            
                            
                            
                            
                            
                            
                            
                            

                            
                         2 :
                            
                            
                            
                            
                            
                            
                            
                            
                            
                            
                            
                            

                            
                         3 :
                            
                            
                            
                            
                            
                            
                            
                            
                            
                            
                            
                            

                            
                         4 :
                            
                            
                            
                            
                            
     ------------------------------------------------------------------------
         2                     2
     RR    <-------------- RR    : 0                                         
       53     | -.6 .8 |     53
              | .8  .6 |

         8                                                                   
     RR    <-----------------------------------------------------------------
       53     | .29173   -.137215  .131623  .0468896 -.0905918 -.551485  .629
              | -.29173  -.164224  -.226171 .42752   .574284   -.0819076 -.21
              | -.437595 -.0180683 -.352459 -.694466 -.130713  -.356089  -.13
              | .29173   -.0673769 .0868048 -.188439 -.321916  .503813   -.20
              | .29173   -.0270088 -.357794 .38063   -.480703  -.40892   -.49
              | -.29173  .834227   -.117388 .248267  -.232305  .0623572  .214
              | -.437595 -.0881199 .763237  .133167  -.256137  -.22776   -.27
              | -.437595 -.494881  -.27465  .270161  -.43661   .292488   .367

         12                                                                  
     RR     <----------------------------------------------------------------
       53      | .278738    -.330931 -.0636129 -.127695  .645269    -.37313  
               | .181387    .0175177 -.109373  .0842121  -.00579485 -.28904  
               | -.0897273  -.357747 .0394609  -.281164  -.32376    -.508571 
               | -.00779127 .080533  .485993   -.0152504 .318467    -.0354616
               | .091828    .285434  -.641126  -.323891  -.0936544  -.0475192
               | -.23277    -.569208 -.360463  .127208   -.144131   .166691  
               | -.41609    .111251  -.220639  -.417497  .399399    -.0792484
               | .262495    .0747623 -.0367352 -.0137386 -.0441806  .248257  
               | .352222    .43251   -.0761961 -.150879  -.0524196  -.110043 
               | .265256    -.242179 .306708   -.7236    -.236879   .269692  
               | .51068     -.142759 -.0770441 .233553   -.161111   -.294916 
               | -.348465   .257248  .22232    -.0287713 -.318621   -.497548 

         12                                                                  
     RR     <----------------------------------------------------------------
       53      | -.409642  .0932651  -.0489842 .127274   .698196   .343166   
               | -.437938  .55024    .565887   -.223659  -.115315  -.072463  
               | -.371333  -.393548  -.0292137 -.216358  -.191764  .456632   
               | .309475   .419368   -.11574   -.208793  -.0489245 .372494   
               | -.0467424 .228516   -.385956  .230435   -.19515   .222109   
               | -.250774  .131081   -.27622   -.241195  -.112536  -.413502  
               | .285925   -.0416247 -.240923  -.617916  .306378   -.0890825 
               | .0952472  -.196698  .199861   .355998   .349078   -.133132  
               | .155527   .0656166  .0763583  .393519   -.288769  -.060593  
               | .218964   -.248338  .489768   -.210814  .0915731  -.125286  
               | -.199112  -.41337   .0745986  -.151334  -.315891  .17688    
               | .372912   .105413   .29767    -.0366188 -.0450206 .482794   

         5                                                             5
     RR    <------------------------------------------------------ RR    : 4
       53     | -.67986  .314387   .266634  -.10376  -.597571  |     53
              | .011089  .0216509  -.466133 -.882608 -.0559598 |
              | -.100377 -.927993  .220916  -.124605 -.253818  |
              | -.562364 -.0587547 .259779  -.193793 .758455   |
              | -.459716 -.189918  -.771581 .396428  .00999282 |
     ------------------------------------------------------------------------
                                                                             



                            8
     ------------------ RR    : 1
     532  -.409743  |     53
     3629 -.521391  |
     5658 -.198458  |
     4282 -.684193  |
     0551 .0483479  |
     904  -.198758  |
     6022 -.0825367 |
     296  .0640359  |

                                                                           12
     ----------------------------------------------------------------- RR    
      .362026   -.0696842 -.0649951 -.0291074  .285884   -.11882   |     53
      -.654952  -.163     -.12309   -.505468   .296012   .224404   |
      -.101172  .154044   -.379518  .00768755  -.409475  -.272327  |
      .101143   .168911   .105545   -.450878   -.523728  .35619    |
      .240237   .461609   .0899657  -.289673   -.0411059 .136479   |
      .230221   -.414876  .0618825  -.224206   -.170613  .344695   |
      -.376649  -.260438  .347766   .191458    -.227687  -.0810968 |
      .0490805  -.302168  .148932   -.467655   -.199291  -.697189  |
      .168261   -.55389   -.367519  .209904    -.256292  .255979   |
      -.0377374 -.0555823 .174669   -.00762927 .240008   .178299   |
      -.10876   .0396109  .625575   .270763    -.247078  .0794334  |
      .350651   -.246016  .336872   -.182589   .286342   -.0278402 |

                                                                         12
     --------------------------------------------------------------- RR     :
     .159003   .410732    .0396321 .0322026  .0418632  -.0362433 |     53
     .031799   -.219953   .0311361 .199921   .151155   -.0589071 |
     .239502   -.37349    .20135   -.351538  -.0403873 -.227316  |
     -.102106  .0885094   -.283291 -.476789  .44594    -.0742702 |
     .280777   -.181658   -.460274 .437215   -.162701  -.338824  |
     .556437   .167079    -.191871 -.308812  -.100452  .349288   |
     .226562   -.168112   .254659  .393838   .244135   -.125274  |
     .271929   -.522598   -.30192  -.0837466 .403889   .193983   |
     .46663    .282084    .475863  .00426586 .369003   -.252619  |
     .230163   .282229    -.388935 -.099933  -.214495  -.492029  |
     -.0501992 .337741    -.295642 .362959   .462061   .284088   |
     .344887   -.00354857 .0828893 .133038   -.346329  .511162   |
     ------------------------------------------------------------------------
        )















     : 2














     3

o8 : Sequence

U is a map from the SVD complex of C, to C. h is a HashTable whose values are the (putative) ranks of the homology groups. Note that the entries of the matrices of this complex are the singular values, but they are not on the main diagonal.

i9 : source U

         2         8         12         12         5
o9 = RR    <-- RR    <-- RR     <-- RR     <-- RR
       53        53        53         53         53
                                                
     0         1         2          3          4

o9 : ChainComplex
i10 : (source U).dd

              2                                    8
o10 = 0 : RR    <----------------------------- RR    : 1
            53     | 34.2783 0 0 0 0 0 0 0 |     53
                   | 0       0 0 0 0 0 0 0 |

              8                                                        12
      1 : RR    <------------------------------------------------- RR     : 2
            53     | 0       0       0       0 0 0 0 0 0 0 0 0 |     53
                   | 160.387 0       0       0 0 0 0 0 0 0 0 0 |
                   | 0       85.9914 0       0 0 0 0 0 0 0 0 0 |
                   | 0       0       40.2416 0 0 0 0 0 0 0 0 0 |
                   | 0       0       0       0 0 0 0 0 0 0 0 0 |
                   | 0       0       0       0 0 0 0 0 0 0 0 0 |
                   | 0       0       0       0 0 0 0 0 0 0 0 0 |
                   | 0       0       0       0 0 0 0 0 0 0 0 0 |

              12                                                        12
      2 : RR     <------------------------------------------------- RR     : 3
            53      | 0       0       0       0 0 0 0 0 0 0 0 0 |     53
                    | 0       0       0       0 0 0 0 0 0 0 0 0 |
                    | 0       0       0       0 0 0 0 0 0 0 0 0 |
                    | 252.014 0       0       0 0 0 0 0 0 0 0 0 |
                    | 0       179.404 0       0 0 0 0 0 0 0 0 0 |
                    | 0       0       55.8422 0 0 0 0 0 0 0 0 0 |
                    | 0       0       0       0 0 0 0 0 0 0 0 0 |
                    | 0       0       0       0 0 0 0 0 0 0 0 0 |
                    | 0       0       0       0 0 0 0 0 0 0 0 0 |
                    | 0       0       0       0 0 0 0 0 0 0 0 0 |
                    | 0       0       0       0 0 0 0 0 0 0 0 0 |
                    | 0       0       0       0 0 0 0 0 0 0 0 0 |

              12                                                5
      3 : RR     <----------------------------------------- RR    : 4
            53      | 0       0       0       0       0 |     53
                    | 0       0       0       0       0 |
                    | 0       0       0       0       0 |
                    | 186.288 0       0       0       0 |
                    | 0       138.149 0       0       0 |
                    | 0       0       113.687 0       0 |
                    | 0       0       0       36.8099 0 |
                    | 0       0       0       0       0 |
                    | 0       0       0       0       0 |
                    | 0       0       0       0       0 |
                    | 0       0       0       0       0 |
                    | 0       0       0       0       0 |

o10 : ChainComplexMap

Caveat

The algorithms in this package work well in many cases, but it would be nice if a numeric analyst would improve the algorithms!

See also

Authors

Version

This documentation describes version 0.3 of SVDComplexes.

Source code

The source code from which this documentation is derived is in the file SVDComplexes.m2.

Exports

  • Functions and commands
    • arePseudoInverses -- check the Penrose relations for the pseudo inverse
    • checkSVDComplex (missing documentation)
    • commonEntries -- lists of positions, where they coincide up to threshold
    • euclideanDistance -- compute the euclidean distance of two chain complexes
    • laplacians -- compute the laplacians of a chain complex
    • newChainComplexMap (missing documentation)
    • numericRank -- approximate rank of a matrix, using SVD
    • projectToComplex -- compute a nearby complex with the projection method
    • pseudoInverse -- compute the pseudoInverse of a chainComplex
    • pseudoInverse1 (missing documentation)
    • SVDComplex -- Compute the SVD decomposition of a chainComplex over RR
    • SVDHomology -- Estimate the homology of a chainComplex over RR with the SVD decomposition
  • Symbols
    • Laplacian -- Option for SVDHomology and SVDComplex
    • Projection -- Option for SVDHomology and SVDComplex