We discuss how homology computation can be exploited in computational electromagnetism. We represent various cellular mesh reduction techniques, which enable the computation of generators of homology spaces in an acceptable time. Furthermore, we show how the generators can be used for setting up and analysis of an electromagnetic boundary value problem. The aim is to provide a rationale for homology computation in electromagnetic modeling software.
1. Introduction
Setting up a wellposed electromagnetic boundary value problem encompasses setting up constraints that are related to the problem domain: the boundary conditions, field sources, and material parameters. These constraints usually surreptitiously involve the topology of the field problem domain. The division of the domain boundary to be governed by different boundary conditions, imposed source fields or circuit quantities, the division of the domain to conducting and nonconducting subdomains, and the use of field potentials bring up topological aspects that cannot be overlooked when defining the boundary value problem [1–6].
Failure to provide the above information in a consistent manner often leads to an over or underdetermined system, and worse than that, the user as well as the software might be clueless where the problem lies. In this light, an automated, fast and definite procedure to find out the keystones of problem topology would save human effort and supersede problemspecific methods and heuristics in EM modeling software.
The tools of homology, capturing the topological nature of Maxwell's equations, can provide what is needed. Therefore, the efficient computation of absolute and relative homology groups has been under active study in computational electromagnetics community during recent years [7, 8]. The absolute homology links to topologically complicated boundary value problem domain, while the relative homology is needed when the boundary values are imposed for the unknown fields, or the boundary value problem is coupled to external systems.
In this paper, we represent a succession of algorithms that, when given a cellular mesh, will lead to computation of generators of homology groups in an acceptable time and memory, establishing the viability of homology computation as an integral part of an electromagnetic modeling software. We also discuss how the information provided by homology computation can be exploited.
2. Homology
The study of homology is sewed around the concept of boundary of a chain, which is an intrinsic part of Maxwell's integral equations and Stokes' theorem. We define a boundary operator on chains, which maps chains to their boundary chains. A chain with zero boundary is called a cycle, and the boundary of the boundary of any chain is empty. Therefore, all boundaries are cycles. However, the converse is not true, there can be cycles that are not boundaries. This makes a dramatic difference in the integration of closed fields over cycles. By Stokes' theorem, the integrals of closed fields vanish over boundaries, but not necessarily over cycles. Therefore, if two cycles differ only by a boundary, integrals of closed fields over them are equal, and they can be considered equivalent in this sense. The homology spaces(they are generalizable into moduli, but we restrict to spaces with coefficient field of or , which are sufficient to our application) of a chain complex provide reliable means to classify cycles depending on their contribution to the integrals of closed fields. The elements of homology spaces are thus cosets of cycles.
To algebraize the concepts of boundary and chain, we form a finitely generated chain complex based on a cellular mesh of the problem domain . The cellular mesh is an instance of the regular cell complex, a finite element mesh for example. The domain is taken to be an orientable manifold with boundary. Now, the finite spaces of chains constitute a chain complex (Chain complex: for each ). under the boundary operator. It is represented by an incidence matrix , one for each dimension . If we chose to disregard part of the chains that lie in a subdomain , covered by cell subcomplex , we get socalled relative chain complex [5, 7]. (In a case boundary values of the unknown field are imposed , we are not interested about the field integrals there.) This is done by forming an inclusion map and quotienting to get . In boundary value problem, the quotient can be formed by dropping the rows and columns from corresponding to elementary chains that lie in (As there are no boundary conditions concerning a multiplicity of a boundary, this is a practical choice of representatives for the relative chains of .) If is empty, we call the chain complex absolute. Our discussion applies to absolute homology as well. Also, the distinction between the domains , and the FE meshes , is disregarded, and and are used throughout. (Chain space is finite dimensional whereas is not, while .)
2.1. Decomposition of Chains and Cohomology
It holds that for each , the relative chain space has the nonunique decomposition [5]
That is, a nonzero relative chain is a relative boundary of some chain, that it belongs to an equivalence class of chains that are neither boundaries of relative chains and do not have a relative boundary in the chain space , or it is a relative chain that has a nonzero relative boundary. Spaces and constitute a space of chains whose boundaries are empty, the relative cycles.
It turns out that the relative homology spaces, moduli in general, are interesting when posing an electromagnetic boundary value problem. (Restriction to space disregards torsion, which may occur in relative homology of orientable manifolds [7]. Our implementation uses integer computations to detect it.)They are isomorphic with cohomology spaces of the (relative) cochains. Cohomology is constructed on the exterior derivative, in our context of the de Rham cohomology, d in the similar manner homology concerns the boundary operator [1, 9]. (In general, this operator is called coboundary operator.) Cochains can be used to model the electromagnetic fields, and the integration of fields can be regarded as a bilinear mapping of chains and cochains [1, 9]. The subdomain is typically a region where a boundary condition is imposed upon an unknown field.
Cohomology and homology are related by de Rham's theorem. A field is closed if , and exact if holds. By de Rham's theorem, a field is exact if and only if
Fields that are closed but fail to be exact belong to the cohomology class . Now, such fields can only exist if the homology space contains nonzero elements. Otherwise by (2.2) and Stokes' theorem, all closed fields are also exact. This is de Rham isomorphism between homology and cohomology: [9]. Therefore, computation of the relative homology of the boundary value problem domain gives us full understanding of how the boundary conditions fix the cohomology classes of the unknown fields, what is left to be determined because of tunnels or voids in the domain.
2.2. Some Properties and Examples of Homology Spaces
The relation between absolute and relative homology spaces can be summarized with the exact sequence of homology spaces [1]:
Here and are an inclusion and a projection induced by the corresponding mappings of chain spaces [5, 7]. That is, all the elements of can be decomposed into such nonunique parts that either have a nonzero preimage in or image in . This twofold structure of emerges when the domain contains tunnels or voids, where field sources might be present in electromagnetic boundary value problem. Such sources can be taken into account with the aid of generators of , which have a counterpart in .
Example 2.1.
A toroid where consists of the two shaded walls in is shown Figure 1. 1chain cosets and generate . Generator has a nonzero preimage in , while generator has image in : .
Figure 1. Two representatives of generators of . One generator has a nonzero preimage in , while the other has image in .
Let be an dimensional manifold. Then there exists an isomorphism [1, 9]
If the boundary is divided into two complementary nonoverlapping parts and , there exists an isomorphism [1, 9]
These are socalled duality theorems, actually, compositions of the Lefschetz and de Rham duality theorems [1, 9], (It is crucial that the coefficient fields are the same on the homology and cohomology side.), which turn out to be useful together with the isomorphism between chains and cochains when considering dual formulations of an electromagnetic boundary value problem.
Example 2.2.
Dual generators of a bar in are shown Figure 2. consists of the opposite shaded ends of the tube, and consists of the jacket. 1chain coset generates , while 2chain coset generates the dual space .
Figure 2. Representatives of dual generators.
3. Computation
From the data structure representing a cellular mesh, that is a regular cell complex, we can deduce the incidence matrices representing the boundary operators. The matrix contains the information about the boundary 1cells of cells. If a 1cell is on the boundary of a cell, the corresponding incidence index is either 1 or −1, depending whether their orientations match or not [5, 7]. Otherwise the incidence index is 0. The boundary operator matrices and knowledge about the cells belonging to and hold all the information we need.
The computation of the : th homology space is about finding the quotient space . In other words, the p : th relative homologyspace is . The computation of a basis of this quotient space using the bases for and can be done with integer matrix decompositions of the boundary operator matrices, as discussed in [7, 8]. The decompositions are called Hermite normal form and Smith normal form. The problem is divided into three parts: finding bases for and , finding an inclusion map , and finding a basis for quotient .
Unfortunately, the computation of the relevant integer matrix decompositions has worse than upper bound for computational time complexity, where is the number of cells in the complex [10]. This is unacceptable, as finite element solution of a boundary value problem is a lot cheaper. However, the number of generators of is practically always substantially smaller than , which suggests that we need to look for means to reduce the size of the bases of chain spaces without altering the relative homology spaces. Only after that, the integer matrix decompositions of the reduced boundary operator matrices are used to compute the generators of homology spaces.
3.1. Problem Size Reduction
Homology spaces are topological invariants and they are isomorphic under weak homotopy equivalences [7, 11, 12]. Those properties provide that homeomorphisms and homotopy invariant mappings between topological spaces also preserve the homology spaces. Therefore, it is possible to apply certain homotopical operations to the problem domain , which keep the homology spaces invariant. When the domain is covered by a regular cell complex , two operations of this kind can easily be exploited [7, 13] as follows.
(i)First is removing a cell that bounds only one cell, together with the cell it bounds. This makes a dent in the domain but not any holes. The corresponding homotopy invariant mapping of the underlying space , is called deformation retraction [12]. In [13], this is referred to as exterior face collapsing.
(ii)Second is combining neighboring cells that share on their boundary a common 1cell that is not bounding any other cells. This mapping leaves intact. It only alters the chain complex , which still covers the same domain. Therefore, the topology of doesnot change. In [13], this is referred to as interior face reduction.
The aim is to perform and implement these two operations in such manner that as many cells as possible get removed with as little computational effort as possible. We have avoided nonlocal reduction methods in order to avoid algebraic computations until the sizes of the bases of chain spaces are modest. The reason we split the reduction techniques in [13] in two separate algorithms is that the former alone is found more computationally efficient, and one should only after that resort to the latter.
3.1.1. Reduction of Cells
If a cell has a boundary 1cell that does not bound any other cell, both of these cells can be removed from the cell complex without altering the relative homology spaces [7, 13]. These cell pairs satisfying the above condition are called elementary reduction pairs. Let be the number of cells in the cell complex .
An estimate for the computational complexity Algorithm 1 is in our interest. The order in which the cells are removed affects the efficiency of the algorithm, which ultimately depends on the index numbering of the cells. It is possible to construct examples where the repeatuntilloop must be ran times, resulting to at least quadratic worst case computational complexity. However, for a typical manifold of a boundary value problem, the loop runs only a couple of times. That gives us more promising estimate when the cell complex is implemented as a binary search tree and the cells carry the information about their boundary cells. The computational complexity is then essentially due to the lineartime forloop and the logarithmictime operation of removing items from a binary search tree. This estimate is .
Algorithm 1:Reduce.
cell complex
Repeat
for all−1cells do
if is on the boundary of exactly one cell and
( or ) then
end if
end for
until no cell has been removed
The removal of a  and a 1cell corresponds to the removal of a row and a column from the matrix of and the removal of a row from the matrix of . The matrix of does not change as the removed cell cannot be on the boundary of any +1cell. In such case, no 1cell can be found that satisfies the ifclause in the algorithm. The algorithm can be applied to the cell complex in succession from the dimension of the cell complex down to . Note though, that the matrix operations are not definitely the most efficient way of implementation.
The number of pairs the algorithm is able to remove from the cell complex ranges from zero to all of them. Usually one successful removal triggers an avalanche of removals. Therefore, the cases where no cells can be removed are the most dramatic, and we enumerate the three possible cases (Figure 3) for each connected component of the problem domain when is equal to the dimension of the cell complex:
(), : elementary reduction pairs can be found. There exist 1cells in that bound only one cell of ;
(): no elementary reduction pairs can be found. A manifold without a boundary: there can be no 1cells bounding only one cell, otherwise they would belong to the boundary;
(): no elementary reduction pairs can be found. This is similar to the first case, but all the 1cells in possible elementary reduction pair candidates for removal belong to .
Figure 3. Three manifolds: a 3dimensional tube , the surface of a toroid (), and a solid (), where consists of the shaded regions. Reduction is able to reduce cells from cell complex , but not from complexes and .
In the last two cases no 1cells can be found that satisfy the ifclause in the nReduce algorithm. The inability to remove any pairs implies that no lower dimensional pairs can be removed either (true for cell complexes whose underlying space is a manifold.) It seems that Reduce algorithm is toothless in many situations, but fortunately we can resort to an approach derived from the Coreduction homology algorithm [14].
3.1.2. The ReduceOmit Algorithm
Coreduction, as opposed to reduction, is the procedure of removing cell and 1cell pairs when the cell has only one 1cell on its boundary. This pair is called an elementary coreduction pair. As no such pairs can be found from a complete cellular mesh, the algorithm is started by arbitrarily removing a single cell, leaving pairs which satisfy the condition. The algorithm goes on by removing one cell each time there are no elementary coreduction pairs left, while there are still cells left. The number of arbitrary removals needed to be done in order to banish all cells equals the Betti number , the number of connected components of the domain [14].
The cell removal is justified by treating the cell complex as the reduced cell complex(constituting together with the augmentation map an augmented chain complex [11].), where there is one additional −cell in each connected component of . Thus, the removal of cell is interpreted as the removal of the coreduction pair . For the reduced homology(homology for the augmented chain complex, an example of an extraordinary homology theory[11]). holds [14]. For the reduced cell complex holds for each connected component, and holds for all [11]. The information lost about due to computing the reduced homology instead can be recovered by storing the arbitrarily removed cells: they are the generators of .
The algebraic dual of a cellular mesh is a mesh where the roles of the cells in the boundary relation of cells have been interchanged. We say is on the coboundary of cell , if is on the boundary of . So in the dual mesh, boundary cells of a cell become coboundary cells and vice versa. Also the dimensions of the cells get flipped over: if the dimension of the manifold is , the dual cell of a cell is an −cell. For the dual mesh, the boundary operator matrices are for each , that is, the transposes of the boundary operators of the primal mesh [5].
Coreduction is a dual algorithm to reduction in the sense that, instead of checking whether a 1cell is on the boundary of a single cell only, it checks whether a cell is on the coboundary of a single 1cell only. So the Coreduction can be interpreted as a reduction algorithm for the dual mesh in terms of primal mesh cells. Due to the isomorphism between primal and dual cells, the coreductions can be regarded as weak homotopy equivalences.
A dual version of the launch of the Coreduction can be used to devise an extension to Reduce algorithm, but only in the case equals : Applying the arbitrary removal to cells from the cell complex each time it notices no elementary reduction pairs could be found in the previous run, yet there still are cells left. The three cases enumerated earlier tell us that this is the case only when is either empty or a subset of . The Reduce algorithm detects this nonexistence of elementary reduction pairs in linear time. Similarly to the Coreduction, the number of arbitrary removals needed to banish all the cells from the cell complex tells us the dimension of , the Betti number . By duality theorem , is equal to the number of connected components of , for which either or holds.
Therefore, each arbitrary removal of a cell leads to a removal of all the cells in the given connected component of and the removed cells together with the "trigger" cell constitute a generator of . This procedure of course leaves the generators out of the final algebraic problem and without orientation, but they can be recovered afterwards. The operation also clearly alters the topology of the domain, but in a controlled fashion. It is known exactly how many and which generators were omitted: one for each connected component of , for which either or holds. We call Algorithm 2 ReduceOmit.
Algorithm 2:ReduceOmit.
cell complex
dimension of the cell complex
for = to 1 do
Reduce ()
end for
while cell complex has cells such that do
choose cell such that
for to 1 do
Reduce (, )
end for
store and cells removed by Reduce (, ) in previous loop.
end while
This strategy cannot be applied further down in the dimension , as there is no guarantee that the generators have separate supports. Therefore, the arbitrary removal of a cell could lead to a removal of such set of cells, from which no representative of the generator of can be constructed. The dimension was exceptional, as all the generators had separate supports, and therefore all the removed cells constituted one generator. For this reason, it seems that the power of the Coreduction algorithm in Betti number computations does not carry over to homology generator computation.
3.1.3. Combining Cells
If a 1cell resides on the boundary of exactly two cells, it is possible to combine these two cells to form single cell and remove the 1cell from the cell complex without altering the covered domain . [7, 13].
Algorithm 3 has worstcase computational complexity of , where is the number of cells in the cell complex. This is due to the fact that eventually most of the 1cells get enqueued in . Another option would be a faster version without a queue, but experience on test runs suggests that the endstate of such algorithm will leave more cells in the cell complex. This tradeoff gets worse as the size of the problem is increased, as one needs to face the algebraic decomposition in the end. Furthermore, accessing the boundary information of a cell is a constanttime operation, if memory is sacrificed to carry this information. The check whether a queue already contains an element, can be done in logarithmic time by maintaining a binary search tree of the elements in the queue. Again, the endstate of the algorithm ultimately depends on the index numbering of the mesh vertices.
Algorithm 3:Combine.
cell complex
empty queue of −1cells
for all cells do
enqueue boundary −1cells of into
while is not empty do
dequeue from
If is on the boundary of exactly two cells , and
(, , or , , then
, the sign chosen such that the orientations match
enqueue boundary −1cells of not already in to
end if
end while
end for
The combining of two cells and removal of a 1cell correspond to an addition rowoperation of two rows followed by removal of a row and a column in the matrix of , an addition column operation of two columns followed by removal of a column in the matrix of and a removal of a row in the matrix of . Again, matrix operations are not an efficient way to reduce the mesh.
Combine can be run for each dimension of the cell complex, starting from down to 1. In addition, after each run of Combine, Reduce (, ) can be run to get rid of "loose tails" that Combine leaves behind; see Figure 4.
Figure 4. A mesh of a square with a hole after cell combining. Loose tails are left behind, which can be removed with Reduce algorithm.
3.2. General Procedure for Homology Computation
Let us now propose a general procedure to find the generators of homology spaces for all . Let be the dimension of the chain complex.
()Run ReduceOmit.
()Run Combine followed by Reduce (, ) for each .
()Find the generators of using the reduced boundary operator matrices for each by HNF and SNF.
()Recover the possible generators of from the cells stored by ReduceOmit (optional).
An implementation of this procedure is available in the open source finite element pre and postprocessor Gmsh [15].
3.2.1. Performance Discussion
The total computational complexity of the procedure above quite plausibly depends on the sizes and the ranks of the homology spaces, along with the index numbering of the mesh. Therefore, it is hard to give any definite estimates other than the complexities for individual algorithms in it. However, the upper and lower bounds can be given.
The ultimate upper bound is the computational complexity bound of the Smith normal form decomposition applied to the nonreduced problem [10]. However, it is highly unlikely that such situation will ever occur in practice with finite element mesh and homology groups without torsion. The worstcase endstates of Reduce and Combine are extremely difficult to discover, as they are homotopy invariances, and homotopy groups are known to be computationally challenging. In case the ranks of the homology spaces are zero for all , the procedure has the computational complexity of Reduce.
In cases where Reduce is unable to ignite, the use of ReduceOmit significantly increases the efficiency of this procedure, as it eliminates the need to give large inputs to Combine. In case only the ranks of the homology spaces are of interest, the Coreduction homology algorithm can be applied [14]. It has the superior computational complexity of , where is the total number of cells in the cell complex.
3.2.2. A Strategy for ThickCuts
Coreduction was found to be a powerful tool to compute the Betti numbers of a cellular mesh, but the answer to whether it is suitable for computation of the generators of homology spaces, seems to be unfortunate. When holds, the supports of the generators may overlap, because the recovery of the orientations of the generators is complexity theoretically intractable in general [7]. However, a modified algorithm can be applied to compute the generators, but in no less computational complexity than the reduction algorithm can.
One can apply Coreduction to the cellular mesh so that only cells are arbitrarily removed in a similar but dual manner as in the ReduceOmit algorithm. Then use straightforward dual versions of Combine and Reduce. Replace "boundary" with "coboundary" and "1cell" with "+1cell" in Algorithms 3 and 1. After that, the homology computation with the reduced and transposed boundary operator matrices will find out the dual generators of the homology spaces, but in terms of primal cells. An example of this is socalled thickcut, which we shall discuss more later.
Example 3.1.
The established method for finding the generators of is to apply ReduceOmit and Combine to and then compute the decompositions of and . Alternatively, one can apply this modified coreduction technique to , as holds. Then compute the decompositions of and to find the same generators, but represented by the primal mesh cells; see Figure 5.
Figure 5. (a): A representative of the generator of of a toroid. (b): A representative of the same generator but in terms of primal mesh cells, socalled thickcut, computed by applying coreduction to .
4. Uses
In this section we motivate the interest of computational electromagnetics community in homology computation. The purpose is to show its benefits in an electromagnetic modeling software.
Homology often relates to the electromagnetic phenomena outside the domain , when we want to couple them with the electromagnetic fields defined on the domain. In contrast, modeling decisions are also made to barricade certain kinds of coupling with the outside world. Nevertheless, the interface is always present, and its homological character is an intrinsic part of an electromagnetic boundary value problem.
Before the understanding of the role of homology and cohomology in electromagnetic modeling, casespecific and limited solutions have been used as substitutes. The genuine use of homology can offer a generally applicable and systematic framework for electromagnetic modeling and computation.
4.1. Setting up an Electromagnetic Boundary Value Problem
Setting up an electromagnetic boundary value problem with unique solution involves a variety of questions that, in general, are about the sources of the electromagnetic fields modeled. How does one set the field sources in together with the boundary conditions consistently? What does imposing a voltage between terminals actually mean? How does one impose a net current through a conducting domain that has terminals on the domain boundary ? Given multiple terminals, how many and which voltages/currents does one need to impose in order to get a unique solution? When is a field potential sufficient to describe alone the unknown field in electromagnetic boundary value problem?
In simple problems, the above questions can be answered with reasoning based on knowledge about Maxwell's integral equations and circuit theory. But what if the problem at hand was so complex that simple reasoning would not help or if we wanted to automate the problem posing and validation in order to save human effort. Of course, the software cannot tell what the user wants, but it can help the user to do what he wants as soon as he tells it.
With the aid of homology computation, the software's answer to all of the above questions would be something like "Impose of these integrals of these field quantities over these generators of homology spaces in order to get a unique solution." Next we will present some tangible examples.
4.2. Cuts for Scalar Potential
The use of scalar potential where possible is preferable in field computation, as it reduces the size of the system matrix: there are far less nodes than edges in a typical mesh. Let a closed field be the field of interest. Due to de Rham's theorem, field can be exhaustively represented with a scalar potential such that holds, if and only if holds for all [9]. That is, the circulation of must vanish on all closed chains.
Whether this holds for all closed chains depends on the homology of the problem domain. It holds by Stokes' theorem for all chains, that are boundaries, but not all cycles are necessarily boundaries. What is left to be determined are the integrals over nonbounding cycles, values , , that is, the field circulations around the generators of the homology space , which is nonempty when the problem domain contains tunnels. However, this fails for a scalar potential alone, as . Therefore, the field is decomposed into two parts, , where satisfies , and . A systematic approach to fix these circulations for and thereby for , is to produce socalled thickcuts, where the support of entirely lies. This will guarantee sparse system matrix, and the problem is computationally cheap to solve.
There is a multiplicity of methods for finding the thickcuts. They often mix in homotopy, or rely on some strict assumptions about the domain . However, the cut surfaces are actually the corresponding duals for the generators of , elements of , reliably computable with our methods. The thickcuts are the dual 1chains of the 2chain generators of .
Example 4.1.
Consider a magnetic core shaped like Figure 8, with coils wound around its branches. The cut surfaces and , the generators of , are shown in Figure 6.
Figure 6. Representatives and of generators of and the corresponding representatives and of the dual generators of .
Example 4.2.
Consider a wire wound around a magnetic core that is surrounded by air. Let consist of the core and air, see Figure 7. Now, the single generator of is a simple loop around the wire. Its dual generator of does not share this virtue, as it "cuts" all such loops.
Figure 7. On the left: a representative of the generator of . On the right, the representative of the generator of .
Figure 8. Coupled fieldcircuit problem. The circuit and field domains are isolated everywhere else except on the shaded region .
Figure 9. Multiformulational field problem. It is often economical to use different field problem formulations in the conducting domain and in the nonconducting domain . 1chain cosets , , and generate .
4.3. Detection of Contradicting Source Quantities and Boundary Conditions
Field sources inside the problem domain and the boundary conditions on domain boundary are often interrelated: the user can set source quantities and boundary conditions in such a fashion that Maxwell's equations cannot hold in the problem domain and a solution is unattainable. Typically, the only symptom is the linear solver's failure to converge. In such cases, a simple sanity check can be made using homology computation before the solver is launched, to inform the user about possible clashes. For a more detailed discussion, see [16].
Example 4.3.
Consider a magnetostatic problem where the domain is a currentcarrying toroid. The problem is governed by the equations and . The source term is set inside the domain, and the boundary conditions and are set on nonoverlapping regions , which cover the whole domain boundary. Now, the magnetostatic equations require that
hold. In order to check whether our boundary conditions comply to those requirements, it is sufficient to check that [16]
where and are representatives of the generators of the homology spaces, readily computable with our methods. If the space is not empty and the user has for example, set on and nonzero net current through , then a clash will occur.
This procedure generalizes to all electromagnetic boundary value problems because all of the Maxwell's equations are of the form
where is the field source, set in the domain , and is the unknown field, subject to a boundary condition on . A clash will occur, if for some .
4.4. Setting Up Coupled CircuitField Problems
Consider a coupled electric circuitfield problem, where Kirchhoff's laws hold in the circuit domain and Maxwell's equations hold in the field domain (Figure 8). To make sure that the field problem constitutes a circuit element, we restrict to the case where the domain contains no tunnels and subject it to the Kirchhoff's current law: . The state variables of the circuit problem are voltages and currents, which describe the power in the system. The circuit problem and the field problem are isolated in such manner that the field problem constitutes a circuit element. The interfaces between the circuit and the field problem are the conductor terminals on . All the power flux by voltages and currents between and is accounted by this interface only, on which voltage and current must have a precise meaning. The isolation is built by boundary conditions
That is, no magnetic or electric flux passes through the boundary , and current can only pass through the terminals . By on we are guaranteed to have scalar potential there. Terminals must be equipotential surfaces to be eligible nodes of the circuit. In order to get an unique solution for the field problem, one needs to set a number of voltages between the terminals and/or currents through them. These constraints are either the state variables of the circuit problem, or preset variables [17].
The generators of the relative homology spaces can be used to interpret the coupling through the terminals on the field problem side. Imposing field integrals along the generators corresponds to providing enough information to construct an impedance matrix of the field problem. We will represent two examples where this is intuitively clear. However, homology computation can bring this "intuition" to the computer, and aid the human intuition in more complex problems. It can tell exactly how many "nonlocal" constraints are needed, and the visualizations of the generators help to understand their meaning.
Example 4.4.
Consider a DC resistor model in Figure 2 with conducting region , two terminals on and an insulating surface . By intuition and experience, one can tell that a unique solution is found by imposing a voltage difference between the terminals. In terms of homology, that is, the integral of electric field along the single generator of : . This reveals that we are actually interested in the EMF between the terminals, and the familiar scalar potential is just one way to impose it. This widens the understanding of the situation beyond the cases where the existence of a scalar potential can be guaranteed everywhere in . However, in coupled fieldcircuit problems, the scalar potential must exist on the surface .
Alternatively, instead of the voltage between the terminals, one can set the net current through the resistor. Again, in the language of homology, this is the integral of current density over the single generator of , which is the dual generator of . So the user needs to set . This together with guarantees that will hold. If neither or both the voltage and the net current are set, one is left with an under/overdetermined system with no unique solution [2], about which homologyaware software is able to inform the user.
Example 4.5.
Consider a general problem with the full set of Maxwell's equations. Let the domain have four terminals on , as in Figure 8, and it may consist of conducting and nonconducting regions. Not all terminals are necessarily galvanically connected to each other. Now we can find three generators of and , respectively. Imposing voltages between the terminals on corresponds to imposing EMFs along the generators of .
More interestingly, imposing integral of over generators of corresponds to imposing currents through terminals, as no displacement current escapes from and the continuity equation must hold for all volumes inside . Conversely, imposing currents through terminals may impose displacement currents in nonconducting parts of the domain , as well as currents in conducting parts. Homologyaware software would be able to help the user to perceive what has been imposed. In total, three EMFs or fluxes of must be imposed to get an unique solution to the problem.
4.5. Multiformulational Field Problem
In many problems, it is possible to use computationally more efficient formulations in some parts the computational domain . For example, the conducting and nonconducting parts of the domain can be treated separately. However, the price for the computational efficiency is the increased effort to set up the problem, as the coupling between the subdomains must be taken into account.
Example 4.6.
Let the domain consist of a conducting subdomain and nonconducting subdomain . In , we can either have an imposed timevarying source current, or it can be coupled to an external circuit through terminals on , as described in previous section. However, let have tunnels, through which the conducting domain extends.
Now, in the air region , we seek for the solution of the magnetic field only, for which holds. We are able to use a scalar potential formulation with the thickcut technique, with expression . But what should be the total currents through the holes in region , fixing the circulations ?
In the conductor region , in addition to the magnetic field, we are interested in the electric field and the corresponding currents. Therefore, we look for the solution of the (coupled) magnetoquasistatic problem defined there. In other words, , , and must hold, where consists of imposed source current and eddy currents generated by the timevarying magnetic flux, and on . The problem is solved by decomposition in , and on by setting and outside the thickcuts [6]. We note that the required currents
which are also the independent currents of the coupled problem, as .
5. Conclusions
A compilation of mesh reduction methods was presented, leading to a general procedure for practical homology computation. The procedure was implemented within this work, and the benefits of homology computation to electromagnetic modeling were discussed. It was suggested that the homology computation, when efficiently implemented, can be a useful preprocessing aid in electromagnetic modeling software. It can be used as a problem posing companion as well as a guardian of the solver, reducing the human effort put to the problem.
Many engineering problems, solved with methods of computational electromagnetism, fall into predefined problem categories, for which templates are readily available in the software. This is helpful for the engineer, but it also narrows down the class of problems a software is able to solve. A minor variant of a commonplace problem can make it unsolvable because of some needless but guiding restriction within the software. Homology computation can help the software designer to give freer hands to the user without reducing the software's usability.
References

Kotiuga, PR: Hodge decompositions and computational electromagnetics, Ph.D. thesis, Electrical and Computer Engineering, McGill University, Montreal, Canada (1984)

Bossavit, A: Most general "nonlocal" boundary conditions for the Maxwell equation in a bounded region. COMPEL. 19(2), 239–245 (2000)

Kettunen, L: Fields and circuits in computational electromagnetism. IEEE Transactions on Magnetics. 37(5), 3393–3396 (2001). Publisher Full Text

Suuriniemi, S, Tarhasaari, T, Kettunen, L: Generalization of the spanningtree technique. IEEE Transactions on Magnetics. 38(2), 525–528 (2002). Publisher Full Text

Kangas, J: Algebraic decompositions in analysis of quasistatic electromagnetic problems, Ph.D. thesis, Department of Electrical Engineering, Tampere University of Technology, Tampere, Finland (2007)

Specogna, R, Suuriniemi, S, Trevisan, F: Geometric  approach to solve eddy currents coupled to electric circuits. International Journal for Numerical Methods in Engineering. 74(1), 101–115 (2008). Publisher Full Text

Suuriniemi, S: Homological computations in electromagnetic modeling, Ph.D. thesis, Department of Electrical Engineering, Tampere University of Technology, Tampere, Finland (2004)

Kaczynski, T, Mischaikow, K, Mrozek, M: Computational Homology, Applied Mathematical Sciences,p. xviii+480. Springer, New York, NY, USA (2004)

Gross, PW, Kotiuga, PR: Electromagnetic Theory and Computation: A Topological Approach, Mathematical Sciences Research Institute Publications,p. x+278. Cambridge University Press, Cambridge, Mass, USA (2004)

Yap, CK: Fundamental Problems of Algorithmic Algebra,p. xvi+511. Oxford University Press, New York, NY, USA (2000)

Munkres, JR: Elements of Algebraic Topology,p. ix+454. Perseus Books, Cambridge, Mass, USA (1984)

Hatcher, A: Algebraic Topology,p. xii+544. Cambridge University Press, Cambridge, Mass, USA (2002)

Kaczyński, T, Mrozek, M, Ślusarek, M: Homology computation by reduction of chain complexes. Computers & Mathematics with Applications. 35(4), 59–70 (1998). PubMed Abstract  Publisher Full Text

Mrozek, M, Batko, B: Coreduction homology algorithm. Discrete and Computational Geometry. 41, 96–118 (2000)

Geuzaine, C, Remacle, JF: Gmsh: a 3D finite element mesh generator with builtin pre and postprocessing facilities. International Journal for Numerical Methods in Engineering. 79(11), 1309–1331 (2009). Publisher Full Text

Suuriniemi, S, Kangas, J, Kettunen, L: Formalization of contradicting source quantities and boundary conditions in quasistatics. IEEE Transactions on Magnetics. 43(4), 1253–1256 (2007)

Suuriniemi, S, Kangas, J, Kettunen, L, Tarhasaari, T: State variables for coupled circuitfield problems. IEEE Transactions on Magnetics. 40(2), 949–952 (2004). Publisher Full Text