多维细分算法收敛的快速计算准则

The subdivision scheme is a scientific discipline in applied mathematics and information science. It is widely used in surface modeling in computer aided geometric design and wavelet analysis. A major open problem concerning with the convergence of subdivision schemes is what is the quickly computable criteria for the convergence. It can be proved by means of the so-called joint spectral radius of some square matrices. However, the calculation of the joint spectral radius is generally NP-hard. The main result of my PhD is to find out those criteria for some nontrivial class of subdivision schemes. The main purpose of this project is to obtain those criteria at first for binary case, and then for multivariate subdivision schemes using some techniques from discrete mathematics and geometry. Moreover, those conditions can be quickly checked. The expected results will solve this problem and provide rigorous mathematical bases and methods.

细分算法是数学与信息科学相互交叉的研究方向，广泛地应用于计算机辅助图形设计与处理以及小波分析中，具有重要的理论和应用价值。长期以来，本方向难以解决的主要问题之一是：如何找到判断细分算法收敛的快速计算准则。众所周知，细分算法收敛的充要条件可利用联合谱半径来刻画，然而该半径的判断问题是NP-Hard。申请人在德国攻读博士学位期间，利用细分面具支集的某种凸性，提出了多维细分算法收敛的充分条件，该条件可快速判别，本项目将继续深入和优化该研究，围绕如何寻找多维细分算法收敛性的快速计算准则展开，拟利用离散数学（数论、图论）分析以及仿射几何等方法与技巧，首先对二维细分算法收敛的充要条件进行研究，提出其快速计算准则，从而为更高维细分算法的相关研究找到突破口，力争解决与此有关的难题，给出判断多维细分算法收敛性的快速计算准则，预期研究成果将从本质上深化已有结果。

细分算法广泛应用于计算机辅助图形设计与处理以及小波分析中，具有重要的理论和应用价值。长期以来，本方向难以解决的主要问题之一是：如何找到判断细分算法收敛的快速计算准则。细分算法收敛的充要条件可利用联合谱半径来刻画，然而该半径的判断问题是NP-Hard。本项目围绕如何寻找多维细分算法收敛性的快速计算准则展开，利用离散数学（数论、图论）以及仿射几何等方法与技巧，分析了单变量非负面具生成的细分算法的收敛性与二维细分算法收敛之间的关系，由此得到二维细分算法收敛时，相应面具支集的组合性质，分析面具支集的内点与边界点之间的联系与区别，给出它们各自的性质，并在此基础之上，找到了由双变量非负面具所生成的可加映射，利用由面具所生成的方阵的连通性阐明了二维细分算法可快速计算的收敛准则，矩阵的连通性可以根据矩阵的大小在线性时间内被检验。提出当面具支集是一般的Zonotope时，相应的二维非负细分算法收敛的充分必要条件是其面具支集满足求和法则以及由其面具支集的凸包所定义的矩阵A是连通的。进而，研究了多维细分面具支集的凸性，通过寻找由细分面具生成的primitive集合或不可分irreducible集合并证明该集合的唯一性，给出了多维非负细分算法收敛的充分条件，这些条件可以根据相应面具支集的大小在多项式时间内被快速验算，解决了本领域长期未能解决的快速检验细分算法收敛性问题，研究成果不仅从本质上丰富和深化已有的相关结论，而且对快速产生计算机图形和设计以及小波分析有理论指导意义，解决生产生活中遇到的实际问题。