**Matrix: Yoshiyasu/image_interp**

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

(bipartite graph drawing) |

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 |

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.
*