**Matrix: JGD_CAG/CAG_mat1916**

Description: CAG matrix set from Michael Monagan, Simon Fraser Univ., Canada

(bipartite graph drawing) | (graph drawing of A+A') |

Matrix properties | |

number of rows | 1,916 |

number of columns | 1,916 |

nonzeros | 195,985 |

structural full rank? | yes |

structural rank | 1,916 |

# of blocks from dmperm | 31 |

# strongly connected comp. | 31 |

explicit zero entries | 0 |

nonzero pattern symmetry | 30% |

numeric value symmetry | 21% |

type | integer |

structure | unsymmetric |

Cholesky candidate? | no |

positive definite? | no |

author | M. Monagan |

editor | J.-G. Dumas |

date | 2008 |

kind | combinatorial problem |

2D/3D problem? | no |

Notes:

CAG matrix set from Michael Monagan, Simon Fraser Univ., Canada From Jean-Guillaume Dumas' Sparse Integer Matrix Collection, http://ljk.imag.fr/membres/Jean-Guillaume.Dumas/simc.html Strongly Connected Graph Components and Computing Characteristic Polynomials of Integer Matrices in Maple, Simon Lo, Michael Monagan, Allan Wittkopf {sclo,mmonagan,wittkopf} at cecm.sfu.ca Centre for Experimental and Constructive Mathematics, Department of Mathematics, Simon Fraser University, Burnaby, B.C., V5A 1S6, Canada. abstract: Let A be an n x n matrix of integers. We present details of our Maple implementation of a simple modular method for computing the characteristic polynomial of A. We consider several different representations for the computation modulo primes, in particular, the use of double precision floats. The algorithm used in Maple releases 7-10 is the Berkowitz algorithm. We present some timings comparing the two algorithms on a sequence of matrices arising from an application in combinatorics of Jocelyn Quaintance. These matrices have a hidden block structure. Once identified, we can further reduce the computing time dramatically. This work has been incorporated into Maple 11's LinearAlgebra package. http://www.cecm.sfu.ca/~monaganm/papers/CP8.pdf Filename in JGD collection: CAG/mat1916.sms

Ordering statistics: | result |

nnz(chol(P*(A+A'+s*I)*P')) with AMD | 406,055 |

Cholesky flop count | 1.2e+08 |

nnz(L+U), no partial pivoting, with AMD | 810,194 |

nnz(V) for QR, upper bound nnz(L) for LU, with COLAMD | 333,006 |

nnz(R) for QR, upper bound nnz(U) for LU, with COLAMD | 529,793 |

SVD-based statistics: | |

norm(A) | 917.127 |

min(svd(A)) | 0.000376116 |

cond(A) | 2.43842e+06 |

rank(A) | 1,916 |

sprank(A)-rank(A) | 0 |

null space dimension | 0 |

full numerical rank? | yes |

singular values (MAT file): | click here |

SVD method used: | s = svd (full (A)) ; |

status: | ok |

For a description of the statistics displayed above, click here.

*Maintained by Tim Davis, last updated 12-Mar-2014.Matrix pictures by cspy, a MATLAB function in the CSparse package.
Matrix graphs by Yifan Hu, AT&T Labs Visualization Group.
*