Search

In this paper, we study an interesting matrix decomposition problem that seeks to decompose a "complicated" matrix into two "simpler" matrices while minimizing the sum of the horizontal complexity of the first sub-matrix and the vertical complexity of the second sub-matrix. The matrix decomposition problem is crucial for improving the "step-and-shoot" delivery efficiency in Intensity-Modulated Radiation Therapy, which aims to deliver a highly conformal radiation dose to a target tumor while sparing the surrounding normal tissues. Our algorithm is based on a non-trivial graph construction scheme, which enables us to formulate the decomposition problem as computing a minimum s-t cut in a 3-D geometric multi-pillar graph. Experiments on randomly generated intensity map matrices and on clinical data demonstrated the efficacy of our algorithm. [ABSTRACT FROM AUTHOR]

Many geometric computations have at their core the evaluation of the sign of the determinant of a matrix. A fast, failsafe determinant sign operation is often a key part of a robust implementation. While linear problems from 3D computational geometry usually require determinants no larger than six, non-linear problems involving algebraic curves and surfaces produce larger matrices. Furthermore, the matrix entries often exceed machine precision, while existing approaches focus on machine-precision matrices. In this paper, we describe a practical hybrid method for computing the sign of the determinant of matrices of order up to 60. The stages include a floating-point filter based on the singular value decomposition of a matrix, an adaptive-precision implementation of Gaussian elimination, and a standard modular arithmetic determinant algorithm. We demonstrate our method on a number of examples encountered while solving polynomial systems. [ABSTRACT FROM AUTHOR]