Matrix: CPM/cz20468

Description: Closest Point Method. Chen, Wathen and Zhu

CPM/cz20468 graph CPM/cz20468 graph
(bipartite graph drawing) (graph drawing of A+A')


CPM/cz20468 dmperm of CPM/cz20468

  • Home page of the UF Sparse Matrix Collection
  • Matrix group: CPM
  • Click here for a description of the CPM 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: 1 MB. Use UFget(2566) or UFget('CPM/cz20468') in MATLAB.
  • download in Matrix Market format, file size: 2 MB.
  • download in Rutherford/Boeing format, file size: 2 MB.

    Matrix properties
    number of rows20,468
    number of columns20,468
    nonzeros206,076
    structural full rank?yes
    structural rank20,468
    # of blocks from dmperm2
    # strongly connected comp.2
    explicit zero entries0
    nonzero pattern symmetry 44%
    numeric value symmetry 24%
    typereal
    structureunsymmetric
    Cholesky candidate?no
    positive definite?no

    authorY. Chen, A. Wathen, S. Zhu
    editorT. Davis
    date2012
    kind2D/3D problem
    2D/3D problem?yes

    Notes:

    Closest Point Method, Yujia Chen, Andy Wathen, Shengxin Zhu        
                                                                       
    A method for computing on surfaces.  For more information see:     
    http://people.maths.ox.ac.uk/~macdonald/closestpoint/              
                                                                       
    One of the matrices in this collection (cz10228) is solved poorly  
    by x=A\b in MATLAB R2012a.  The solution is to use this setting:   
                                                                       
        spparms ('piv_tol', 0.5)                                       
        x = A\b                                                        
                                                                       
    which changes the pivot tolerance.  MATLAB has a test which        
    checks the accuracy of x=A\b when using UMFPACK, and if the        
    accuracy is poor, it refactorizes the matrix with a piv_tol        
    of 1.0 (standard partial pivoting).  For the cz10228 matrix,       
    the test is nearly, but not quite, triggered.  The other matrices  
    do not cause this problem.                                         
                                                                       
    Further details from Shengxin Zhu:                                 
                                                                       
    Generally speaking, the matrix comes from the numerical solution of
    Poisson equation on a unit circle by solving an embedding PDE posed
    in a narrow band around the circle. Of course the easiest way to   
    solve PDE on a unit circle is to parametrize it and then solve a 1D
    problem; but here we just want to test the effectiveness of the    
    embedding method for solving PDEs on general curves or surfaces.   
    The method extends the original surface PDE to a band around the   
    surface, and then solve the extended PDE on a Cartesian grid by a  
    finite difference scheme. In order to define such a PDE, one has to
    both define proper embedding differential operator and extend the  
    solution from the surface to the embedding space. One natural way  
    is to enforce the solution being constant along the normal         
    direction of the surface so that the surface differential operator 
    could be replaced by standard Cartesian differential operator. Here
    in the case of Poisson equation on a unit circle, we solve a       
    standard Poisson equation on a 2D cartesian grid around the circle 
    with suitable right hand side and Neumann boundary condition on the
    boundary of the band. We enforce the Neumann boundary condition by 
    taking the value of each boundary point to be the value of its     
    closest point on the circle; and since the closest point is usually
    not a grid point, its value is obtained by interpolation of values 
    of the surrounding points. Putting the process into a sparse       
    matrix, and change one row of the matrix to fix the value of one   
    point of the solution and ensure the matrix is nonsingular.        
                                                                       
    I tried different bandwidth, different interpolation order for the 
    value of the closest points, 2nd order and 4-th order finite       
    difference scheme to the Laplace operator. In most cases, MATLAB   
    backslash works pretty well in solving the resulting linear system.
    The size of the matrix which makes MATLAB backslash not work is not
    the largest among all, and its condition number is not largest     
    among all. By the way, the AMG solver by Notay and a geometric     
    multigrid solver written by myself works pretty well for this case.
    

    Ordering statistics:result
    nnz(chol(P*(A+A'+s*I)*P')) with AMD332,170
    Cholesky flop count5.8e+06
    nnz(L+U), no partial pivoting, with AMD643,872
    nnz(V) for QR, upper bound nnz(L) for LU, with COLAMD269,063
    nnz(R) for QR, upper bound nnz(U) for LU, with COLAMD670,648

    SVD-based statistics:
    norm(A)3.26504e+06
    min(svd(A))0.00698707
    cond(A)4.67298e+08
    rank(A)20,468
    sprank(A)-rank(A)0
    null space dimension0
    full numerical rank?yes

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

    CPM/cz20468 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.