华为发布的工业软件三大难题: 面向装配场景，10万+零件的超大规模几何约束系统的求解问题

?华为发布的工业软件三大难题: 面向装配场景，10万+零件的超大规模几何约束系统的求解问题。

一方面是算法改进，

另一方面是对云几何内核的需求：并行计算、分布式、缓存、集群等云计算技术对CAD系统的辅助提升。

云几何内核可以(/需要能)支撑“研究充分利用云计算和GPU加速等软硬件资源的系统架构和算法。”这方面的改进。

云几何内核的很重要的场景之一是：并行计算，比如，对大模型的各个部分，并行处理，然后合并结果。

另一个场景可以考虑的是：异步，比如一个大模型，处理一部分，在界面上展现一部分，直致全部处理完。异步可以提升交互友好性与效率：不必等到系统全部处理完，人才能看与判断：效果不行，直接提前取消后续处理。

以下内容转载：

技术背景：

?

几何约束求解是CAD系统最重要的共性关键技术之一。约束求解引擎的稳定性（stability），一致性（consistency），和高效性（efficiency）是影响CAD系统的关键指标。

1、稳定性：在给定的误差内的非线性方程组的收敛问题

2、一致性：在多解情况下总能给出符合设计意图的解

3、高效性：CAD系统的交互设计特点要求约束求解速度要非常快（小于1秒）

超大规模几何约束系统的求解效率是制约CAD系统处理超大模型（如10万+零部件的汽车装配模型）的关键技术难点之一, 解决超大规模几何约束系统的求解效率一方面需要研究更高效的分解算法，另一方面也要研究大规模非线性方程组的高效求解算法，同时也要研究充分利用云计算和GPU加速等软硬件资源的系统架构和算法。

?

技术挑战：

除了稳定性和一致性，超大规模约束系统求解的最主要的挑战是解决高效性的问题

1、几何分解算法：将一个大规模问题转化为一系列可分步求解的子问题，通过降低子问题的规模来提高约束求解的效率。

2、非线性方程组的求解：提高非线性方程组的求解速度是超大规模约束系统求解的主要挑战解决高效性问题的发展趋势：几何分解算法-最近一二十年高效算法的研究进展缓慢；方程组的求解-利用约束方程组的稀疏特性提高求解效率显示出比较好的前景，如稀疏矩阵相关的cholesky 分解、Lanczos算法等，如非线性方程组的信赖域算法等；利用软硬件资源：云计算和GPU等硬件技术的发展也为解决大规模约束系统的求解问题提供了强大的环境支持。

技术诉求：

1. 当前几何约束求解引擎的设计目标是5000左右的几何约束系统计算速度在1秒内完成，以支持中等规模的CAD系统的交互设计需求
2. 创新方案的目标是超大规模几何约束系统(10万+)的求解速度在1秒内，以满足大规模CAD系统交互设计的需求

?

参考文献：

[1] R. Light and D. Gossard, Modification of geometric models through variational geometry. Computer Aided Design, 14(7):209–214, 1982.
[2] J.C. Owen, Algebraic solution for geometry from dimensional constraints, Symposium on Solid Modeling Foundations and CAD/CAM Applications, pages 397–407, Austin, TX, 5-7 1991.
[3] W. Bouma, I. Fudos, C.M. Hoffmann, J. Cai, and R. Paige. Geometric constraint solver. Computer Aided Design, 27(6):487–501, 1995.
[4] C.M. Hoffmann, R. Joan-Arinyo, A Brief on Constraint Solving, Computer Aided Design and Applications, 2(5):655-663, 2005.
[5] M. Rojas, S.A. Sanos, D. C. Sorensen. A New Matrix-Free Algorithm for the Large-Scale Trust-Region Subproblem, SIAM Journal on Optimization, 11(3):611-646, 2000.
[6] N.I. Gould, S. Lucidi, M. Roma, P.L. Toint. Solving the Trust-Region Subproblem using the Lanczos Method, SIAM Journal on Optimization, 9(2):504–525, 1999.
[7] Timothy A. Davis, Algorithm 849: A concise sparse Cholesky factorization package, ACM Transactions on Mathematical software, 2005.
[8] Franz Rendl, Henry Wolkowicz, A semidefinite framework for trust region subproblems with applications to large scale minimization, Mathematical Programming 77, pages 273-279, 1997.

联系人：吴瑾????lion.wujin@huawei.com

原文链接：面向装配场景，10万+零件的超大规模几何约束系统的求解问题--中国科学院数学与系统科学研究院-华为 π实验室