Matrix: CPM/cz148

Description: Closest Point Method. Chen, Wathen and Zhu

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

• 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: 9 KB. Use UFget(2559) or UFget('CPM/cz148') in MATLAB.
• download in Matrix Market format, file size: 11 KB.
• download in Rutherford/Boeing format, file size: 11 KB.

 Matrix properties number of rows 148 number of columns 148 nonzeros 1,527 structural full rank? yes structural rank 148 # of blocks from dmperm 2 # strongly connected comp. 2 explicit zero entries 0 nonzero pattern symmetry 43% numeric value symmetry 23% type real structure unsymmetric Cholesky candidate? no positive definite? no

 author Y. Chen, A. Wathen, S. Zhu editor T. Davis date 2012 kind 2D/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 AMD 2,361 Cholesky flop count 4.2e+04 nnz(L+U), no partial pivoting, with AMD 4,574 nnz(V) for QR, upper bound nnz(L) for LU, with COLAMD 1,972 nnz(R) for QR, upper bound nnz(U) for LU, with COLAMD 4,556

 SVD-based statistics: norm(A) 192.964 min(svd(A)) 0.0780471 cond(A) 2472.4 rank(A) 148 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.