# 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!

• SVDComplex -- Compute the SVD decomposition of a chainComplex over RR
• SVDHomology -- Estimate the homology of a chainComplex over RR with the SVD decomposition

## 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