×

Inverting the discrete curl operator: a novel graph algorithm to find a vector potential of a given vector field. (English) Zbl 07561081

Summary: We provide a novel framework to compute a discrete vector potential of a given discrete vector field on arbitrary polyhedral meshes. The framework exploits the concept of acyclic matching, a combinatorial tool at the core of discrete Morse theory. We introduce the new concept of complete acyclic matchings and we show that they give the same end result of Gaussian elimination. Basically, instead of doing costly row and column operations on a sparse matrix, we compute equivalent cheap combinatorial operations that preserve the underlying sparsity structure. Currently, the most efficient algorithms proposed in literature to find discrete vector potentials make use of tree-cotree techniques. We show that they compute a special type of complete acyclic matchings. Moreover, we show that the problem of computing them is equivalent to the problem of deciding whether a given mesh has a topological property called collapsibility. This fact gives a topological characterization of well-known termination problems of tree-cotree techniques. We propose a new recursive algorithm to compute discrete vector potentials. It works directly on basis elements of 1- and 2-chains by performing elementary Gaussian operations on them associated with acyclic matchings. However, the main novelty is that it can be applied recursively. Indeed, the recursion process allows us to sidetrack termination problems of the standard tree-cotree techniques. We tested the algorithm on pathological triangulations with known topological obstructions. In all tested problems we observe linear computational complexity as a function of mesh size. Moreover, the algorithm is purely graph-based so it is straightforward to implement and does not require specialized external procedures. We believe that our framework could offer new perspectives to sparse matrix computations.

MSC:

65Nxx Numerical methods for partial differential equations, boundary value problems
52Bxx Polytopes and polyhedra
78Mxx Basic methods for problems in optics and electromagnetic theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Lipnikov, K.; Manzini, G.; Shashkov, M., Mimetic finite difference method, J. Comput. Phys., 257, 1163-1227 (2014) · Zbl 1352.65420
[2] Pitassi, S.; Ghiloni, R.; Trevisan, F.; Specogna, R., The role of the dual grid in low-order compatible numerical schemes on general meshes, J. Comput. Phys., 436 (2021) · Zbl 07513849
[3] Di Pietro, D. A.; Droniou, J., An arbitrary-order method for magnetostatics on polyhedral meshes based on a discrete de Rham sequence, J. Comput. Phys., 429 (2021) · Zbl 07500728
[4] Tran-Cong, T., On the potential of a solenoidal vector field, J. Math. Anal. Appl., 151, 557-580 (1990) · Zbl 0727.35030
[5] Cohen, M. B.; Fasy, B. T.; Miller, G. L.; Nayyeri, A.; Peng, R.; Walkington, N. J., Solving 1-laplacians in nearly linear time: collapsing and expanding a topological ball, (SODA (2014)) · Zbl 1428.65070
[6] Webb, J. P.; Forghani, B., A single scalar potential method for 3d magnetostatics using edge elements, IEEE Trans. Magn., 25, 4126-4128 (1989)
[7] Le Menach, Y.; Clenet, S.; Piriou, F., Determination and utilization of the source field in 3d magnetostatic problems, IEEE Trans. Magn., 34, 2509-2512 (1998)
[8] Rodríguez, A. A.; Bertolazzi, E.; Ghiloni, R.; Valli, A., Construction of a finite element basis of the first de Rham cohomology group and numerical solution of 3d magnetostatic problems, SIAM J. Numer. Anal., 51, 2380-2402 (2013) · Zbl 1284.78012
[9] Dłotko, P.; Specogna, R., Physics inspired algorithms for (co)homology computations of three-dimensional combinatorial manifolds with boundary, Comput. Phys. Commun., 184, 2257-2266 (2013)
[10] Alonso Rodríguez, A.; Bertolazzi, E.; Ghiloni, R.; Valli, A., Finite element simulation of eddy current problems using magnetic scalar potentials, J. Comput. Phys., 294, 503-523 (2015) · Zbl 1349.78060
[11] Silberman, Z. J.; Adams, T. R.; Faber, J. A.; Etienne, Z. B.; Ruchlin, I., Numerical generation of vector potentials from specified magnetic fields, J. Comput. Phys., 379, 421-437 (2019) · Zbl 07581580
[12] Rodríguez, A. A.; Valli, A., Finite element potentials, Appl. Numer. Math., 95, 2-14 (2015) · Zbl 1320.65164
[13] Dlotko, P.; Specogna, R., Critical analysis of the spanning tree techniques, SIAM J. Numer. Anal., 48, 1601-1624 (2010) · Zbl 1219.78142
[14] Dlotko, P.; Specogna, R., Efficient generalized source field computation for h-oriented magnetostatic formulations, Eur. Phys. J. Appl. Phys., 53 (2011)
[15] Forman, R., Morse theory for cell complexes, Adv. Math., 134, 90-145 (1998) · Zbl 0896.57023
[16] Kozlov, D., Combinatorial Algebraic Topology, Algorithms and Computation in Mathematics (2008) · Zbl 1130.55001
[17] Benedetti, B.; Lutz, F., Knots in collapsible and non-collapsible balls, Electron. J. Comb., 20, P31 (2013) · Zbl 1295.57004
[18] Cantarella, J.; DeTurck, D.; Gluck, H., Vector calculus and the topology of domains in 3-space, Am. Math. Mon., 109, 409-442 (2002) · Zbl 1038.53017
[19] Benedetti, R.; Frigerio, R.; Ghiloni, R., The topology of Helmholtz domains, Expo. Math., 30, 319-375 (2012) · Zbl 1276.57001
[20] Christiansen, S., A construction of spaces of compatible differential forms on cellular complexes, Math. Models Methods Appl. Sci., 18, 739-757 (2008) · Zbl 1153.65005
[21] Tonti, E., The Mathematical Structure of Classical and Relativistic Physics: A General Classification Diagram (2013) · Zbl 1298.00082
[22] Lipnikov, K.; Manzini, G.; Shashkov, M., Mimetic finite difference method, J. Comput. Phys., 257, 1163-1227 (2014) · Zbl 1352.65420
[23] Whitehead, J., Simplicial spaces, nuclei and m-groups, Proc. Lond. Math. Soc., s2-45, 243-327 (1939) · JFM 65.1443.01
[24] Strang, G., Introduction to Linear Algebra (1993) · Zbl 1067.15501
[25] Cormen, T.; Leiserson, C.; Rivest, R.; Stein, C., Introduction to Algorithms (2009) · Zbl 1187.68679
[26] Lewiner, T.; Lopes, H.; Tavares, G., Optimal discrete Morse functions for 2-manifolds, Comput. Geom., 26, 221-233 (2003) · Zbl 1031.65031
[27] Tancer, M., Recognition of collapsible complexes is NP-complete, Discrete Comput. Geom., 55, 21-38 (2016) · Zbl 1335.68286
[28] Benedetti, B.; Lutz, F. H., Random discrete Morse theory and a new library of triangulations, Exp. Math., 23, 66-94 (2014) · Zbl 1296.57018
[29] Fujiwara, K.; Nakata, T., Results for benchmark problem 7 (asymmetrical conductor with a hole), Compel, 9, 137-154 (1990)
[30] Cohen, M. M., A Course in Simple-Homotopy Theory (1973) · Zbl 0261.57009
[31] Bing, R., Some Aspects of the Topology of 3-Manifolds Related to the Poincaré Conjecture (1964) · Zbl 0126.39104
[32] Goodrick, R., Non-simplicially collapsible triangulations of In, Math. Proc. Camb. Philos. Soc., 64, 31-36 (1968) · Zbl 0179.52602
[33] Furch, R., Zur Grundlegung der kombinatorischen Topologie, Abh. Math. Semin. Univ. Hamb., 3, 69-88 (1924) · JFM 49.0399.01
[34] Ziegler, G. M., Shelling polyhedral 3-balls and 4-polytopes, Discrete Comput. Geom., 19, 159-174 (1998) · Zbl 0898.52006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.