Matrix: Yoshiyasu/image_interp

Description: image editting problem, Y. Yoshiyasu, Keio Univ, Japan

 (bipartite graph drawing)

• Matrix group: Yoshiyasu
• download as a MATLAB mat-file, file size: 3 MB. Use UFget(2248) or UFget('Yoshiyasu/image_interp') in MATLAB.

 Matrix properties number of rows 240,000 number of columns 120,000 nonzeros 711,683 structural full rank? yes structural rank 120,000 # of blocks from dmperm 1 # strongly connected comp. 7,516 explicit zero entries 0 nonzero pattern symmetry 0% numeric value symmetry 0% type real structure rectangular Cholesky candidate? no positive definite? no

 author Y Yoshiyasu editor T. Davis date 2009 kind computer graphics/vision problem 2D/3D problem? yes

 Additional fields size and type b full 240000-by-2

Notes:

```The problem is template-mesh deformation to match with silhouettes.  In this
process, there are two kinds of linear systems to solve.  This system
(Yoshiyasu/image_interp) is a smooth vector field construction from images,
which is harmonic interpolation (minimizing laplacian: Lx=0) of intensity
gradient field p.  This can be solved by normal equation and cholesky
factorization, x=(A1'*A1)/(A1'*b1), where A1=[L;C] and
b1=[zeros(size(length(L),1);1);C*p]. C is a square diagonal matrix containing
weights.  This is for a 400x300 image, so Ix=reshape(x,400,300) must be done
to get the vector field. After solving y direction for Iy, the result is
visualized with quiver(Ix,Iy).   At each iteration the both C submatrix and
the right-hand-side change but L remains unchanged.  [Note by T. Davis:
since C is of high rank, update/downdate will not be effective, since it is
meant for low-rank changes.]
```

 Ordering statistics: result nnz(V) for QR, upper bound nnz(L) for LU, with COLAMD 316,991,703 nnz(R) for QR, upper bound nnz(U) for LU, with COLAMD 12,952,004