An effective synthesis of an arabinogalactan with a β-(1->6)-linked galactopyranose backbone and α-(1->2) arabinofuranose side chains

Article abstract of DOI:10.1016/j.crma.2004.09.021

An octasaccharide, β-D-Galp-(1->6)-[α-L-Araf-(1->2)]-β-D-Galp-(1->6)-β-D-Galp-(1->6)-[α-L-Araf-(1->5)-α-L-Araf-(1->2)]-β-D-Galp-(1->6)-β-D-Galp-1-> OMP was synthesized. 4-methoxyphenyl 2,3,4-tri-O-benzoyl-β-D-galactropyranoside (5), 2,6-di-O-acetyl-3,4-di

Full text of DOI:10.1016/j.crma.2004.09.021

C. R. Acad. Sci. Paris, Ser. I 339 (2004) 673–678
http://france.elsevier.com/direct/CRASS1/
Numerical Analysis
Domain decomposition methods of dual-primal FETI type
for edge element approximations in three dimensions
Andrea Toselli
Seminar for Applied Mathematics, ETH Zürich, CH-8092 Zürich, Switzerland
Received 8 September 2004; accepted 21 September 2004
Presented by Olivier Pironneau
Abstract
We consider domain decomposition algorithms of FETI type for edge element approximations in three dimensions. We first
show that a strong coupling exists between tangential degrees of freedom associated to the subdomain edges and faces. We then
propose a dual-primal FETI algorithm that relies on a change of basis and on a suitable choice of a coarse space. We give a
logarithmic bound for the condition number of the resulting preconditioned operator. Numerical results confirm this bound and
the necessity of performing a change of basis. To cite this article: A. Toselli, C. R. Acad. Sci. Paris, Ser. I 339 (2004).
2004 Académie des sciences. Published by Elsevier SAS. All rights reserved.
Résumé
Méthodes FETI dual-primal pour approximations aux éléments finis d’arête en dimension trois. Nous considérons des
algorithmes FETI pour des approximations en éléments finis d’arête en dimension trois. Nous montrons d’abord qu’il existe
un couplage fort entre les degrés de liberté tangentiels associés aux arêtes et aux faces des sous-domaines. Nous proposons
ensuite un algorithme FETI dual-primal qui utilise un changement de base et un choix particulier pour le solveur grossier. Nous
donnons une borne logarithmique pour le nombre de conditionnement de l’algorithme. Les tests numériques confirment cette
borne et la nécessité du changement de base. Pour citer cet article : A. Toselli, C. R. Acad. Sci. Paris, Ser. I 339 (2004).
2004 Académie des sciences. Published by Elsevier SAS. All rights reserved.
Version française abrégée
Nous considérons le problème (1) en dimension trois et l’espace H(curl;Ω). On introduit un maillage régulier
Th de Ω et une partition TH , sans recouvrement, en sous-domaines Ωi. Chaque sous-domaine (sous-structure)
est l’union d’éléments fins de Th. Les diamètres de Th et TH sont h et H , respectivement. On choisit les espaces
d’éléments finis d’arête Xh d’ordre le plus bas, introduits dans [6]. Les degrés de liberté peuvent être choisis comme
E-mail address: toselli@sam.math.ethz.ch (A. Toselli).
1631-073X/$ – see front matter
doi:10.1016/j.crma.2004.09.021
2004 Académie des sciences. Published by Elsevier SAS. All rights reserved.

674
A. Toselli / C. R. Acad. Sci. Paris, Ser. I 339 (2004) 673–678
a composante tangentielle sur les arêtes de Th et, sur un sous-domaine Ωi peuvent être partagés entre trois classes :
intérieur, arête, et face (voir la Fig. 1).
Les algorithmes FETI sont des méthodes de décomposition de domaine sans recouvrement pour la résolution
de systèmes algébriques provenants de l’approximation des équations aux dérivées partielles. Ils sont couramment
utilisés pour des problèmes de très grande taille, en élasticité et en mécanique des fluides, mais le développement
d’une stratégie robuste pour les problèmes électromagnétiques tridimensionnels manque à ce jour.
Les méthodes de décomposition de domaine sans recouvrement utilisent la possibilité de trouver des dé-
compositions stables pour les fonctions d’éléments finis en composantes associées aux faces et aux arêtes des
sous-domaines; voir [2, Section 5]. Ces décompositions existent pour les éléments nodaux, mais ne sont pas dispo-
nibles pour les éléments d’arête en dimension trois. Cela est montré Fig. 1. On considère le gradient d’une fonction
nodale continue, nulle sur tous les noeuds de Ωi sauf en un noeud situé sur une arête E. Le rotationnel de ce
vecteur est nul et sa norme H(curl;Ωi) est O(h). Si on découple ce vecteur en composantes associées à l’arête E
et aux deux faces de E, on obtient des vecteurs avec un rotationnel non nul et d’une norme H(curl;Ωi) qui est
O(h−1) ; voir la Section 2.
Nous considérons donc un changement de base. Seules les fonctions de base associées aux arêtes des sous-
domaines sont changées; voir la Définition 3.1. Avec cette nouvelle base on introduit une méthode de type FETI
ꢀ
dual-primal; voir [3,1,7]. On utilise un espace Xh d’éléments finis discontinus à travers les sous-domaines et on
impose la continuité de la composante tangentielle avec des multiplicateurs de Lagrange λ ; voir l’Éq. (3). La
méthode FETI utilise la résolution de l’équation pour λ par une méthode itérative comme le gradient conjugué et
un préconditionneur M−1 ; voir l’Éq. (4).
La forme du préconditionneur M−1 est standard et peut être trouvée en [3,4] ou [7, Section 3]. Il reste seulement
ꢀ
ꢀ
à caractériser l’espace Xh. Les vecteurs de Xh satisfont quelques conditions de continuité (primal constraints) à
travers les sous-domaines, ces conditions déterminent la taille du solveur grossier. Ici on impose la continuité de la
ꢀ
moyenne (moment d’ordre zéro) et du moment du premier ordre de la composante tangentielle des vecteurs de Xh
le long des arêtes E des sous-domaines. On obtient donc deux conditions pour chaque arête E.
On trouve que le nombre de conditionnement de l’operateur préconditionné est borné par une fonction loga-
rithmique de H/h et est indépendant du nombre des sous-domaines et des sauts d’un des coefficients; voir le
Théorème 5.1.
Le Tableau 1 montre les nombres de conditionnement pour la méthode FETI avec (à gauche) et sans (à droite)
changement de base décrit dans la Section 3. Il s’agit ici de maillages et de partitions uniformes pour des coeffi-
cients constants. Les résultats de gauche montrent des nombres de conditionnement très petits, indépendants de la
taille n2 du problème quand H/h est donné. Les résultats de droite, par contre, montrent des nombres de condi-
tionnement très grands qui croissent comme n2 = h−2 confirmant donc notre analyse présentée dans la Section 2.
1. Introduction
We consider the boundary value problem:
curl(a curlu) + bu = f in Ω,
(1)
n × (u × n) = 0 on ∂Ω,
with Ω a bounded polyhedral domain in R3 with outward unit normal n and a and b positive functions. More
general boundary conditions can also be considered.
The variational formulation and the analysis of problem (1) require the Sobolev space H(curl;Ω) of vectors in
L2(Ω)3 (the space of square summable vectors on Ω), with a curl that is also in L2(Ω)3. For u ∈ H(curl;Ω), we
use the norm given by
2
2
2
ꢀuꢀH(curl;Ω) = ꢀuꢀ
with ꢀ · ꢀ
+ ꢀcurluꢀ
,
L2(Ω)3
L2(Ω)3
2
the norm in L2(Ω)3. See, e.g., [5] for an introduction and for further details.
L2(Ω)3

A. Toselli / C. R. Acad. Sci. Paris, Ser. I 339 (2004) 673–678
675
We next consider a conforming triangulation Th of Ω, consisting of affinely mapped cubes or tetrahedra, and a
nonoverlapping subdomain partition TH = {Ωi}, with subdomains that are collections of fine elements. The sub-
domains (substructures) and the fine elements are always assumed to be shape-regular and H and h, respectively,
denote the maximum of their diameters.
We choose the lowest-order edge element (Nédélec) finite element spaces Xh ⊂ H(curl;Ω) on the fine triangu-
lation Th; see [6]. We also refer to [5] for a fine presentation. Here, we recall that these finite elements preserve the
continuity of the tangential component across the element boundaries and the degrees of freedom can be chosen as
the (constant) tangential component along the element edges of Th.
We note that in a subdomain Ωi, the degrees of freedom can be partitioned into three classes: interior, edge, and
face, according to whether they lie in the interior of Ωi, on a subdomain edge E, or face F. We refer to Fig. 1, left,
for the case of a cubical substructure.
The finite element approximation of problem (1) gives rise to a positive definite, symmetric linear system, for
the vector u of degrees of freedom:
Ku = f.
(2)
2. Nonoverlapping algorithms for edge elements in three dimensions
FETI algorithms are particular domain decomposition methods of nonoverlapping type for the solution of al-
gebraic systems arising from the approximation of a partial differential equation (see Eq. (2)): they rely on a
nonoverlapping partition of Ω into subdomains or substructures. While they are now routinely employed for the
solution of huge elasticity and flow problems (see, e.g., [3,1,4]) a full understanding of robust and efficient strate-
gies for nonoverlapping domain decomposition preconditioners for three-dimensional electromagnetic problems is
still missing.
Nonoverlapping domain decomposition preconditioners rely on decoupling degrees of freedom associated to
geometrical objects associated to subdomains, typically vertices, edges, and faces for three-dimensional continuous
nodal elements; see, e.g., [2, Section 5]. For edge elements, we only need to consider subdomain edges and faces.
The performance of the corresponding preconditioned iterative method depends on how weak the coupling between
the different blocks of degrees of freedom is. This decoupling may appear explicitly in the construction of finite
element subspaces as in wire basket methods, [2], but it may also be hidden in the algorithm and may not appear
explicitly in the subspaces considered, as in FETI methods.
Decompositions into edge and face components are fairly harmless (i.e., logarithmically stable) operations for
continuous nodal h finite elements, see [2], but turn out to be disastrous for edge element approximations. More
precisely, we refer to Fig. 1, right, and consider the gradient of a continuous, scalar, piecewise trilinear function
φE with vanishing nodal values on the closure of a subdomain Ωi except at one node on a coarse edge E where
it is one. Since φE decreases linearly from one to zero along an edge of length O(h), its tangential component is
O(h−1). This vector is curl free and has a low energy:
2
2
ꢀ∇φEꢀ
= ꢀ∇φEꢀ
= O(h−2 · h3) = O(h).
L2(Ωi)3
H(curl;Ωi )
We recall that the square of the L2 norm of a basis function is O(h3) while that of its curl is O(h). When we put
to zero the degrees of freedom on the two faces adjacent to E, we obtain a vector w with a nonvanishing curl and
therefore with a much larger energy:
2
2
ꢀwꢀH(curl;Ω ) ∼ ꢀcurlwꢀ
= O(h−2 · h) = O(1/h).
L2(Ωi)3
i
A nonoverlapping domain decomposition algorithm which employs the standard three-dimensional edge ele-
ment basis is expected to exhibit a condition number that grows at least as h−2, which is the same growth exhibited
by the original stiffness matrix K.

676
A. Toselli / C. R. Acad. Sci. Paris, Ser. I 339 (2004) 673–678
Fig. 1. Two types of basis functions associated to a subdomain edge: the standard basis (left) and one consisting of gradients of continuous,
scalar, nodal functions associated to nodes internal to the coarse edges and one vector function with unitary tangential component along the
coarse edges.
3. A change of basis
The discussion in the previous section hints that, before devising iterative substructuring algorithms for Prob-
lem (2), a change of basis may be necessary.
Definition 3.1 (New basis).
1. The basis functions associated with the edges inside Ωi and with those in the interior of the faces are the same
as for the standard basis;
2. the basis functions associated with a subdomain edge E are:
(a) one vector function ꢀE with unitary tangential component along E and vanishing tangential component
along all the fine edges that lie on the remaining coarse edges, on the faces, and in the interior of Ωi;
(b) the gradients of continuous, scalar, nodal functions associated to the interior nodes of E; these scalar
functions take the value zero at all the nodes in the closure of Ωi except at one node in the interior of E,
where they are equal to one.
This new basis is described in Fig. 1. The new basis functions are introduced only for the coarse subdomain
edges and the new degrees of freedom can still be partitioned into interior, face, and edge. The construction of this
new basis does not rely on the fact that the substructures are elements of a coarse mesh or have a special shape.
4. Dual-primal FETI algorithms
We assume from now on that vectors of primal degrees of freedom are relative to the new basis introduced in
the previous section. We define the intersection between the subdomain boundaries by Γ and note that it consists
of faces F which are shared by exactly two subdomains, and subdomain edges and vertices, which are shared by
more than two subdomains; see, e.g., Fig. 1. We then rewrite Eq. (2) as:
T
ꢀ
˜
(3)
Ku˜ + B λ = f ,
Bu˜ = 0.
ꢀ
Here, the vector of degrees of freedom u˜ belongs to a larger finite element space Xh ⊃ Xh, consisting of vectors
ꢀ
ꢀ
that have a discontinuous tangential component along Γ ; K is the stiffness matrix relative to the space Xh. The
second equation enforces the continuity of the tangential component along Γ and λ is the Lagrange multiplier
associated to these constraints. See [3,1,7] for details.
An equation for λ can be obtained by eliminating the primal variable u˜. We obtain:
M
−1(Fλ − d) = 0,
F = BK−1BT.
(4)
ꢀ

A. Toselli / C. R. Acad. Sci. Paris, Ser. I 339 (2004) 673–678
677
Here, M−1 is a suitable symmetric, positive definite preconditioner. Once λ is found by an iterative method like
Conjugate Gradient the solution u˜ can be found.
The form of the preconditioner M−1 is standard and can be found in, e.g., [3,4] or [7, Section 3]. We recall, in
particular, that one application of M−1 requires the solution of a Dirichlet problem on each subdomain. In addition,
suitable scaling matrices need to be applied, which are constructed with the coefficients a and b in (1); see next
section for more details.
ꢀ
The matrix K (and therefore its inverse, required for the application of F) depends on the exact choice of
ꢀ
the discontinuous space Xh. In dual-primal FETI algorithms, a certain number of continuity constraints (primal
−1
ꢀ
ꢀ
constraints) are enforced for the vectors u˜ ∈ Xh. The application of K
to a vector requires the solution of
Neumann problems on the subdomains and an additional coarse, global problem the size of which equals the
number of primal constraints. The selection of primal constraints is of key importance in the development of dual-
primal FETI algorithms; see [3,4]. The primal constraints are for our edge element approximations associated to
the subdomain edges.
ꢀ
We first impose that the average (zero-th order moment) of the tangential component of vectors in Xh is con-
tinuous along every coarse edge E, independently of which substructure is used in the evaluation of this average.
We note that these primal constraints are the coarse degrees of freedom associated to TH , in case the subdomain
partition TH coincides with a coarse mesh. As for similar algorithms for three-dimensional, continuous nodal el-
ements, these primal constraints are not sufficient to ensure good condition number bounds; see [3,4]. We impose
that also the first order moments of the tangential component are continuous along every coarse edge E. This
choice therefore gives two primal constraints associated to a subdomain edge, and therefore a coarse problem of
small size.
5. Theoretical and numerical results
In order to obtain bounds for the condition number of the FETI operator M−1F, we need to make further
assumptions on the coefficients. We first assume that a is uniformly bounded from zero. This assumption is required
only for the theory but in practice good convergence is also obtained for a small or zero. Furthermore, while similar
algorithms for two-dimensional approximations can be made robust with respect to the jumps of both coefficients
in a straightforward way (see [7] and the references therein), this is not the case in three dimensions. We assume
therefore that only one of the coefficients a and b may have arbitrarily large jumps across the substructures Ωi,
while the other is assumed to be continuous across −th1e substructures or to have small jumps. The scaling matrices
used for the construction of the preconditioner M use the coefficient that has jumps. We have the following
result:
Theorem 5.1. Let a be uniformly bounded from below. There is then a constant independent of h, the number of
subdomains, or the jumps of one of the coefficients, such that the condition number bound
ꢁ
ꢂ
q
κ(M−1F) ꢀ C 1 + log(H/h)
holds with q = 4.
,
The proof relies on decomposition results for the tangential traces of edge element vectors in the new basis
associated to the subdomain edges and faces.
We now present some simple numerical tests. We consider the domain Ω = (0, 1)3 and uniform triangulations
Th and TH . The coarse triangulation TH consists of N3 cubical elements, with H = 1/N. The fine one Th is
a refinement of TH and consists of n3 cubical elements, with h = 1/n. The substructures Ωi are chosen as the
elements of TH . We assume a = b = 1. Table 1, left, shows that the condition numbers of the preconditioned FETI
operator M−1F are small and bounded independently of h = 1/n: their growth with H/h is consistent with q = 2

678
A. Toselli / C. R. Acad. Sci. Paris, Ser. I 339 (2004) 673–678
Table 1
−1
Condition number of M F versus H/h and n, with (left) and without (right) a change of basis
H/h
8
6
4
3
2
H/h
8
6
4
3
2
n = 8
–
–
–
2.213
2.742
2.838
2.899
2.926
2.944
–
–
2.48
–
–
–
1.869
1.936
1.960
1.969
–
n = 8
−
–
–
1429
–
–
151.6
607.6
1365
2427
3793
5462
–
–
1429
–
–
–
1.869
1.936
1.960
1.969
–
n = 16
n = 24
n = 32
n = 40
n = 48
3.076
3.566
3.774
3.866
3.951
n = 16
n = 24
n = 32
n = 40
n = 48
643.7
3.322
–
–
1449
2576
4024
5795
3.537
–
5712
–
in Theorem 5.1. In Table 1, right, we show the condition number of the same algorithm but without performing the
change of basis of Section 3. The condition numbers are very high and are consistent with a quadratic growth in n,
thus confirming our analysis in Section 2. We note that the algorithms relative to the last column (H/h = 2) are
special cases for which the tangential component is continuous along the subdomain edges and for which a change
of basis is not necessary.
References
[1] M. Bhardwaj, K. Pierson, G. Reese, T. Walsh, D. Day, K. Alvin, J. Peery, C. Farhat, M. Lesoinne, Salinas: A scalable software for high-
performance structural and solid mechanics simulations, in: Proceedings of the IEEE/ACM SC2002 Conference, Baltimore, MD, November
16–22, 2002.
[2] M. Dryja, B.F. Smith, O.B. Widlund, Schwarz analysis of iterative substructuring algorithms for elliptic problems in three dimensions,
SIAM J. Numer. Anal. 31 (6) (1994) 1662–1694.
[3] C. Farhat, M. Lesoinne, P. LeTallec, K. Pierson, D. Rixen, FETI-DP: a dual-primal unified FETI method. I. A faster alternative to the
two-level FETI method, Int. J. Numer. Methods Engrg. 50 (7) (2001) 1523–1544.
[4] A. Klawonn, O.B. Widlund, M. Dryja, Dual-primal FETI methods for three-dimensional elliptic problems with heterogeneous coefficients,
SIAM J. Numer. Anal. 40 (1) (2002) 159–179.
[5] P. Monk, Finite Element Methods for Maxwell’s Equations, Numerical Mathematics and Scientific Computation, The Clarendon Press,
Oxford University Press, New York, 2003.
3
[6] J.-C. Nédélec, Mixed finite elements in R , Numer. Math. 35 (1980) 315–341.
[7] A. Toselli, X. Vasseur, Dual-primal FETI algorithms for edge element approximations: two-dimensional h and p finite elements on shape-
regular meshes, Tech. Report 04-01, Seminar for Applied Mathematics, ETH Zürich, 2004, SIAM J. Numer. Anal., in press.