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.