Matrix: JGD_CAG/CAG_mat1916

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

JGD_CAG/CAG_mat1916 graph JGD_CAG/CAG_mat1916 graph
(bipartite graph drawing) (graph drawing of A+A')

JGD_CAG/CAG_mat1916 dmperm of JGD_CAG/CAG_mat1916

  • Home page of the UF Sparse Matrix Collection
  • Matrix group: JGD_CAG
  • Click here for a description of the JGD_CAG group.
  • Click here for a list of all matrices
  • Click here for a list of all matrix groups
  • download as a MATLAB mat-file, file size: 289 KB. Use UFget(1941) or UFget('JGD_CAG/CAG_mat1916') in MATLAB.
  • download in Matrix Market format, file size: 499 KB.
  • download in Rutherford/Boeing format, file size: 229 KB.

    Matrix properties
    number of rows1,916
    number of columns1,916
    structural full rank?yes
    structural rank1,916
    # of blocks from dmperm31
    # strongly connected comp.31
    explicit zero entries0
    nonzero pattern symmetry 30%
    numeric value symmetry 21%
    Cholesky candidate?no
    positive definite?no

    authorM. Monagan
    editorJ.-G. Dumas
    kindcombinatorial problem
    2D/3D problem?no


    CAG matrix set from Michael Monagan, Simon Fraser Univ., Canada        
    From Jean-Guillaume Dumas' Sparse Integer Matrix Collection,                    
    Strongly Connected Graph Components and Computing                      
    Characteristic Polynomials of Integer Matrices in Maple,               
    Simon Lo, Michael Monagan, Allan Wittkopf                              
    {sclo,mmonagan,wittkopf} at                                
    Centre for Experimental and Constructive Mathematics,                  
    Department of Mathematics, Simon Fraser University,                    
    Burnaby, B.C., V5A 1S6, Canada.                                        
    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.                                                 
    Filename in JGD collection: CAG/mat1916.sms                            

    Ordering statistics:result
    nnz(chol(P*(A+A'+s*I)*P')) with AMD406,055
    Cholesky flop count1.2e+08
    nnz(L+U), no partial pivoting, with AMD810,194
    nnz(V) for QR, upper bound nnz(L) for LU, with COLAMD333,006
    nnz(R) for QR, upper bound nnz(U) for LU, with COLAMD529,793

    SVD-based statistics:
    null space dimension0
    full numerical rank?yes

    singular values (MAT file):click here
    SVD method used:s = svd (full (A)) ;

    JGD_CAG/CAG_mat1916 svd

    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.