НАУКА и ОБРАЗОВАНИЕ

Файл статьи: SE-BMSTU...o266.pdf (1673.11Кб)

УДК 004.021

Россия,  МГТУ им. Н.Э. Баумана

Настоящая работа посвящена рассмотрению двух методов автоматического разделения конечно-элементной модели на суперэлементы с целью снижения потребности в вычислительных ресурсах при решении линейно-упругих задач механики деформируемого твердого тела. Первый метод представляет собой алгоритм разделения конечно-элементной сетки на односвязные подобласти по характерному заданному числу узлов в суперэлементе. Второй метод основывается на формировании суперэлементов с заданным характерным объемом хранения матрицы коэффициентов системы уравнений равновесия внутренних узлов, исключаемых в ходе суперэлементного преобразования. Оба метода основываются на теории графов. Оценка объема хранения матрицы коэффициентов осуществляется в предположении, что при дальнейшем решении задачи применяется метод Холецкого. Перед оценкой объема хранения предварительно осуществляется перенумерация внутренних узлов суперэлемента при помощи алгоритма Катхилла-Макки (Cuthill-McKee) с целью снижения ширины профиля соответствующей матрицы системы уравнений равновесия и уменьшения числа ненулевых элементов. На тестовых примерах представлено сравнение результатов работы указанных методов с точки зрения неравномерности генерируемого суперэлементного разбиения по числу узлов и объему хранения матрицы коэффициентов системы уравнений равновесия внутренних узлов. Показано, что предлагаемый подход обеспечивает меньшую неравномерность объемов хранения матриц суперэлементов, при незначительном увеличении неравномерности по числу вершин.

1. Zienkiewicz O.C., Taylor R.L. The finite element method. Vol. 1: The basis. Butterworth-Heineman, 2000. 689 p.
2. Васильев Ф.П. Методы оптимизации. М.: Факториал Пресс, 2002. 824 с.
3. Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений: пер. с англ. М .: Мир , 1984. 333 с .
4. Qu Z. Model Order Reduction Techniques: with Applications in Finite Element Analysis. Springer London , 2004. P. 257-262.
5. Karypis G., Kumar V. A fast and high quality multilevel scheme for partitioning irregular graphs. Philadelphia // SIAM Journal on Scientific Computing (SISC). 1999. Vol. 20, no. 1. P. 359-392.
6. Bichot C.E., Siarry P. Graph Partitioning: Optimisation and Applications. ISTE – Wiley, 2011. P. 13-16.
7. GdalyahuY.,Weinshall D.,WermanM. Self-organization in vision: stochastic clustering for image segmentation, perceptual grouping, and image database organization // IEEE Transaction on Pattern Analysis and Machine Intelligence. 2001. Vol. 23, no. 10. P. 1053-1074. DOI: 10.1109/34.954598
8. Martínez A.M., Mittrapiyanuruk P., Kak A.C. On combining graph-partitioning with non-parametric clustering for image segmentation // Computer Vision and Image Understanding. 2004. Vol. 95, no. 1. P. 72-85. DOI: 10.1016/j.cviu.2004.01.003
9. Zhao Y., Karypis G. Empirical and theoretical comparisons of selected criterion functions for document clustering // Machine Learning. 2004. Vol. 55, no. 3. P. 311-331. DOI: 10.1023/B:MACH.0000027785.44527.d6
10. Bichot C.E. Co-clustering documents and words by minimizing the normalized cut objective function // Journal of Mathematical Modeling and Algorithms (JMMA). 2009. Vol. 9, no. 2. P. 131-147. DOI: 10.1007/s10852-010-9126-0
11. Bichot C.E. Metaheuristics versus spectral and multilevel methods applied on an air traffic control problem // Proceedings of the 12th IFAC Symposium on Information Control Problems in Manufacturing (INCOM), May 2006. P. 493-498.
12. Sedgewick R. Algorithms. 4th ed. Boston: Addison-Wesley Professional, 2011. 976 p.
13. Ng A.Y., Jordan M., Weiss Y. On Spectral Clustering: Analysis and an Algorithm // Proc. 14th Advances in Neural Information Processing Systems, 2001. P. 849-856.
14. Rosenberg A., Heath L. Graph Separators, with Applications. Springer US , 2002. 270 p. DOI:10.1007/b115747
15. Dhillon I.S., Guan Y., Kulis B. Weighted graph cuts without eigenvectors: a multilevel approach // IEEE Transactions on Pattern Analysis and Machine Intelligence. 2007. Vol. 29, no. 11. P. 1944-1957. DOI: 10.1109/TPAMI.2007.1115
16. Watkins D.S. Fundamentals of matrix computations. 2^nd ed. New York: John Wiley & Sons, Inc., 2002. P. 60-61.
17. clang: a C language family frontend for LLVM: website. Режим доступа:http://clang.llvm.org (дата обращения 10.03.2015).
18. Qt: Cross-platform application & UI development framework: website. Режим доступа: http://www.qt.io (дата обращения 11.03.2015).
19. JTC1/SC22/WG21 - The C++ Standards Committee – ISOCPP: official website. Режим доступа:http://www.open-std.org/jtc1/sc22/wg21/ (дата обращения 10.03.2015).
20. ParaView : website . Режим доступа: http://www.paraview.org (дата обращения 11.04.2015).