Ghislaine Gueudet
email: ghislaine.gueudet@espe-bretagne.fr

Birgit Pepin²

Students' work in mathematics and resources mediation at entry to university

Keywords: epistemic mediation, pragmatic mediation, resources, secondary-tertiary transition

In this paper we study the use of resources by students in their mathematical work at the beginning of university. The institution offers a variety of resources: lecture notes, books, exercises, websites, to name but a few. Leaning on a theoretical framework by Rabardel, we argue that the university teachers expected an epistemic mediation of these resources, as they supported student learning of (higher level) mathematics. However, analysing two case studies (one in the UK and one in France) we observe that the actual use of resources by novice mathematics students corresponded to a pragmatic mediation, as they searched for worked examples and "reproduction techniques", all very similar to their use of resources at secondary school.

STUDENTS' WORK WITH RESOURCES AT THE SECONDARY-TERTIARY TRANSITION

The secondary-tertiary transition is a moment of important institutional evolutions: e.g. in terms of the mathematics taught; the mathematical practices expected from students; the institutional support for student learning [START_REF] Gueudet | Investigating the secondary-tertiary transition[END_REF][START_REF] Pepin | Using the construct of Didactic Contract to understand student transition into university mathematics education[END_REF]. In this article we claim that the resources available for students" work with mathematics, and the expected use of these resources (expected by the institution) significantly change from secondary school to university mathematics education. When entering university, it is assumed that students develop new ways to use resources, mathematical texts in particular. Previous research (e.g. [START_REF] Rezat | The Utilization of Mathematics Textbooks as Instruments for Learning[END_REF]) contends that at secondary school even grade 12 students used their mathematics textbook mostly to search for worked examples, in order to learn rules and how to apply these rules to tasks similar to the tasks they worked on with their teachers in class. The same holds true at the beginning of university: [START_REF] Lithner | Students" mathematical reasoning in university textbook exercises[END_REF] shows that students" homework with textbooks was mostly oriented towards solving exercises; and that students searched for surface similarities between exercises, in order to choose a procedure. Our hypothesis is that this use of textbooks and other mathematical curriculum material by university students derives from similar practices at secondary school, in particular their use of textbooks. Hence, our research question is the following:

-which use of resources is expected by university mathematics teachers, and how does this compare with the actual use of resources by students?

In the next section we explain the theoretical frame we used, Rabardel"s (2002Rabardel"s ( /1995) ) instrumental approach. Subsequently, we present a case study from the UK TransMaths project 1 , considering students" work in mathematics at a general level; and a case study in France concerning students" work in the area of Number Theory.

RESOURCE MEDIATION: THEORETICAL FRAME AND METHODS

In terms of theoretical frame we refer to the instrumental approach by Rabardel (2002Rabardel ( /1995)). He distinguishes between an artefact -produced by humans, for an aim of human activity; and an instrument -developed by a subject along his/her goaldirected activity with this artefact. The instrument incorporates the artefact (or parts of it) and a scheme of use for this artefact [START_REF] Vergnaud | Toward a cognitive theory of practice[END_REF]. Following [START_REF] Vygotsky | Mind in society[END_REF], [START_REF] Rabardel | From computer to instrument system: A developmental perspective[END_REF] consider that the goal-directed activity of a subject is mediated by instruments, in particular between the subject and the object of his/her activity. This mediation has a pragmatic value: the instrument permits to reach the aim of the activity; it contributes to the production of an outcome. At the same time it has an epistemic value: it contributes to the development of the subject him/herself and of his/her understanding of the object. This pragmatic/epistemic distinction has been stressed in particular by [START_REF] Artigue | Learning Mathematics in a CAS Environment: The Genesis of a Reflection about Instrumentation and the Dialectics between Technical and Conceptual Work[END_REF] in her work about the use of CAS (Computer Algebra Systems). She identified pragmatic and epistemic values in the instrumented techniques developed by students: these techniques both permitted to reach an aim, for example solve an exercise; and to build new mathematical knowledge, enabling the students to solve further exercises. Drawing on the work of Rabardel, we developed the theoretical frame of the documentational approach (Gueudet, Pepin & Trouche 2012). In this approach, instead of artefacts we considered resources of different kinds, following the definition proposed by [START_REF] Adler | Conceptualising resources as a theme for teacher education[END_REF]: everything that is likely to re-source the activity. Our previous research has mostly been concerned with teacher interaction with resources; our focus here is on students" use of resources. We distinguish between available/proposed resources and resources-in-use, comparing the resources available for students (resources offered by the institution), and the resources actually used. We already analysed the two cases presented here in terms of links between the Didactic Contract [START_REF] Brousseau | Theory of didactical situations in mathematics 1970-1990[END_REF]) and the use of resources [START_REF] Gueudet | Didactic contract and secondary-tertiary transition: a focus on resources and their use[END_REF]. In this paper we extend the epistemic/pragmatic distinction to the mediation realised by various kinds of resources (Gueudet, Pepin & Trouche 2012) intervening in students" work, and investigate these mediations. The resource mediation can be represented by the following figure (figure 1). Students at university use resources of various kinds: paper resources presenting the text of the lecture; their own notes; lists of exercises; textbooks; online resources found on the Internet; etc. These resources mediate the interaction between the student and the object of his/her activity; it has both a pragmatic and an epistemic value.

Both teachers" expectations and students" actual use of resources can be investigated through interviews with teachers and students, and we conducted such interviews in our two cases in the UK and in France.

In the UK, we explored the use of resources at a general level, at a medium-size university in a large city in the South of England. We mean by "general level": for all mathematical content areas (taught during the first year), focusing on the general organisation of students" work. Beside conducting student interviews (with selected students), we surveyed all students of that particular mathematics course; we observed lectures, and interviewed lecturers, in addition to other support staff (e.g. teaching assistants at university) and teachers at secondary school. We also collected documents at both institutions (school, university, in the UK). For the work presented here, we selected a case study subject who is an ethnic minority student, Simar and his (ethnic minority) friends, all studying mathematics in the faculty of mathematics at the same university. We followed Simar over approximately two years: starting when he transited from a local upper secondary school into a university mathematics course, and into his second year at university. Over that period observations and interviews were conducted at several data points: (1) in his previous school (with his mathematics teacher/s); (2) at entry to university (with Simar and his friends; and with lecturers and support tutors); (3) towards the end of the first year at university (with Simar and his friends); and (4) during the first semester of his second year at university (as under ( 2)). For this study, interviews Other students

Teacher

Student

Object of the activity: work in mathematics

Resources: textbook, list of exercises, Internet

with Simar (3); focus interviews with his friends (2); and interviews with selected lecturers (5) were analysed using our theoretical frame explained earlier.

The case in France has been conducted with a focus on a particular mathematical content, Number Theory. We collected data in a medium-size university where Number theory was taught in a first year teaching unit. During the academic year 2014-2015, we interviewed the teacher responsible of the course about the use of resources she expected from students. We also proposed an online questionnaire to the 140 students about their use of resources. We collected 85 answers (around 61 %). In 2015-2016 we complemented this study by proposing exercises as homework to a group of students, and interviewing three of them about their use of resources for solving these exercises. The collection of data at different levels, we claim, is likely to give us insights at different phenomena, which (it is hoped) complement each other.

CASE 1: STUDENT RESOURCES AND THEIR MEDIATION AT GENERAL LEVEL

From interviews with Simar (and his friends), who studied at City University, we could identify the main resources used in their first year of study: the lecture and lecture notes; the coursework; notes and tutorial notes made during tutorial and/or with his friends/study group. It was clear that these resources were quite different, in nature and quantity, from what students were used to at school: at school students had one textbook (which was portraying mathematics as something that one can learn by solving "tons of exercises"), whereas at university they were expected to work with many resources: e.g. different textbooks; lecture notes; examination papers; etc.

At City University the main resources were clearly the lecture, usually in halls of up to 300 students, and the lecture notes provided by the lecturer/professor (sometimes supported by a textbook). Different lecturers had different styles of lecture notes. Some lecturers would produce hand-written notes projected onto a screen (and talk students through the content during the lecture) (e.g. calculus). Simar and his friends would copy these notes, most of the time with little or no understanding.

However, Simar talked quite enthusiastically about one of his lecturers, and he pointed to what he (and his peers) would regard as a good lecture and lecture notes.

S: Geometry: the feedback we got from geometry is, basically he's faultless. He's brilliant, he's excellent; the lecture's engaging, the notes are available-clear notes. You can use the notes for the coursework.

Int: The notes are handwritten? S: Yeah handwritten notes yeah. And they actually, you can see the kind of proofs-he doesn't give too much away, but it's just enough to get you thinking in the coursework's, which is excellent. ... Because like, what students are finding is that they can go, because the lectures, they're not gonna walk around with the lecture twenty-four, seven are they? They need something to take away from the lecture and you know, they're gonna ready at home, they're gonna read it, and they understand it. ... And they can go to the tutorial, ask whatever questions and do the questions with confidence, knowing that they've done well like because everything's there, available. They don't need to go anywhere else, and if they do, the tutorial's available or the office hours. So really it's probably one of the best.

Int: So do you think they understand because in the lecture he explains well, or do you think they understand because the, it's so well-prepared and written out? S: I think mainly it's mostly well-prepared, definitely, and then to accompany that, the lectures are brilliant as well. Yeah it's really, really kind of funny. He catches your interest..." (DP5, Simar)

Another lecturer would provide notes that students had to read in advance of the lecture. These notes had "holes" that needed to be filled in. During the lecture the lecturer would then discuss the content, and subsequently fill in the "holes". In such a way, students were not only obliged to prepare the lecture in advance (in order to be able to understand the notes in the lecture and fill in the missing text), but they also needed to attend the lectures to have "complete" notes.

In addition to lectures, the coursework (provided once a week) was to support student understanding of the lecture, through exercises. Simar and his friends/learning group were clear that unless the coursework was well aligned with the lectures, it did not help their understanding of the subject area (see Calculus as compared to geometry lectures/coursework). Indeed, in some cases students did not know what to ask in tutorial time, or in lectures, so little had they understood of the topic area. Other resources included textbooks (suggested/approved by the lecturers), but these were seen as less helpful than the lecture notes and coursework (provided by lecturers and tutors), in particular as students were often "learning to the test". However, the same resources (e.g. lecture notes) were often evaluated very differently by students, in terms of support for their learning, so much so that Simar (as student representative) had asked for a change in form and practice concerning lecture notes: as students did not want to be presented with "one slide after another".

Interestingly, in terms of lecture notes students distinguished between different types of notes: (1) "understanding notes" were well prepared and developed, apparently useful for understanding and coursework (and tests); (2) "comfort notes" were those that students did not understand but "you"ve got to have the notes" and "you have gone to the lecture", which in their views helped for knowing what to study for revision and examination purposes; and (3) "motivation notes" were provided on the student web, before the lecture, and which apparently "makes you want to come to the lecture … because they are different" (DP5, p.4).

At the same time institutional practices, such as lectures, and accompanying resources played a crucial role in the ways that mathematics, and what it meant to "do mathematics" was portrayed. On the basis of video footage of selected lectures and pre-and post-video stimulated recall discussions with lecturers one could identify meanings that were attached to particular practices. Particular lectures reflected the kinds of things that a "rigorous mathematician" may need to learn:

-"reasoning and proof" based thinking and practices were expected to be developed through Geometry and Linear Algebra;

-"procedural fluency" (methods) was seen to be developed through Calculus;

-practical and context relatedness was regarded to be developed through Statistics.

However, it was clear that during lectures student would not learn how to work as a "rigorous mathematician", neither did students expect this from lectures and lecture notes. What students wanted were "help notes" for doing their course work, and worked examples suitable for studying for examinations.

"The only way I understand to do my work is, when I"m doing my coursework and there are help questions to do your coursework, and this is how I tend to them more and during the tutorials, and I think the tutorials and the courseworks are more helpful than, the lecture. The lecture you just get the notes." (DP5 Focus group interview)

In terms of mediation of resources, in particular lecture notes, it can be argued that for students they had mainly pragmatic value: Simar and his friends were content, if they were given the "instruments" to do their coursework and examination questions. However, for university lecturers the mediation of (for example) lecture notes had epistemic value: they wanted to develop students into "rigorous mathematicians", and lecture notes (and lectures) would show them how "rigorous mathematicians" worked. How that could be learnt was not clear, except for alignment with what the lecture notes showed as examples. In fact, at City University one lecturer realized the problematic, and he had started a module on "writing mathematics" which was to provide students with the language they needed to appreciate the epistemic side of the subject.

CASE 2: STUDENT RESOURCES AND THEIR MEDIATION IN NUMBER THEORY

Our investigations took place in a first year teaching of Number Theory spanned over twelve weeks, with four hours each week (two hours of lecture, and two hours of tutorial). The first half of the course concerned logic, sets and combinatorics; the second half more directly number theory, with Euclidean division, Euclid algorithm, prime numbers and congruencies.

Use of resources by students and pragmatic mediation

In 2014-2015, at the beginning of this course the students were provided with a "polycopie", which included more or less the text of the lecture; and a list of exercises. They could also access complementary resources, on the webpage of the teacher responsible for the teaching: previous exam texts; references of books; links towards online exercises. We proposed an online questionnaire to the 140 students concerned and obtained 85 answers. Only 52% of these 85 students declared that they found the polycopie useful. They considered that the text of the lecture of their teacher was enough, and used the polycopie only before the final exam (83%). Moreover 90% would have liked to find worked examples in the polycopie; and 44% looked for additional resources on the Internet, in particular worked examples. We contend that these answers evidence that the polycopie mediation remains pragmatic for the students, similar to their use of textbooks at secondary school where number theory is limited to the application of some techniques [START_REF] Battie | Number theory in the national compulsory examination at the end of the French secondary level between organizing and operative dimensions[END_REF]. Alike students in the UK, they search for worked examples in order to reproduce techniques, whereas the teacher expects that the polycopie has a strong epistemic value, and is used to work on the course: learn definitions, understand proofs of theorems etc. (declared by the teacher responsible for this teaching).

Mathematical resources for Number Theory

In 2015-2016, following the results of the questionnaire evoked above (a report about the answers was presented to the teachers of the number theory unit), no polycopie was given to the students. A book was recommended instead, together with a website, Braise 2 proposing exercises associated with different mathematical texts: description of methods, extracts of the course, hints, partial solution etc.

The teacher proposed to the students the following exercise as homework: This exercise can be solved by searching for a and b such that a(2n+3)+b(n 2 +3n+2)=1. There is a specific difficulty in this exercise, since a had to be itself of the form un+v, where u and v were constant integers.

A student can solve this exercise without any explicit use of resources; nevertheless, since the homework was given at a stage where such tasks are not yet familiar to students, we consider that this will probably not happen. Amongst the resources provided by the institution, the students can use their course notes, in particular to find the definition of coprime. They can also use the notes taken during the tutorial, where an exercise using a similar method has been done: "Let m and n be integers, such that m divides both 8n+7 and 6n+5. Show that m=±1"(Exercise 8). In this exercise, the students also need to find a linear combination of 8n+7 and 6n+5, which does not depend on n. The students can also visit the Braise website; they could find on it a method entitled "Determine if two integers are coprime" which can also be used here as a resource. It does not mean that the students will only need to reproduce the same method: in particular, the presence of n 2 in exercise 28 requires a significant adaptation of the method. We claim that, in such a case, the resources mediation has an important epistemic value.

16 students did the proposed homework; ten of them proposed a correct solution, and for six of them proposed a wrong solution. We met three of these students for an individual interview about the resources they used to solve the exercise: Brian, and Franck, who did not succeed; and Tom who found a correct solution. Tom used exercise 8 that he found in his tutorial notes, and correctly adapted the method.

Franck used exercises that he found on the Internet (but not on BRAISE), which he identified as useful in terms of including the idea of Euclidean division of polynomials, and divides n 2 +3n+2 by 2n+3.This lead him to conclude that the gcd is (-1/4), "so is ± 1 up to a constant multiplier"). Brian searched his lecture notes, found the property "if p is prime and n an integer, then p and n are coprime". He tried to apply it but realised that 2n+3 is not always prime. Then he searched grade 12 textbooks, found the linear combination method but only with constant coefficients, and thought that the coefficient cannot depend on n. We claim that, while for Tom and Franck epistemic mediations of the resources took place, for Brian the mediation was limited to a pragmatic aspect. He searched for a method that he wanted to apply without any adaptation. Franck took personal initiative searching for resources that where not proposed by the teacher. He tried to build an original method, but was not successful in controlling its correctness. It is noticeable that, while Brian came directly from secondary school to university, Tom and Franck have had previous experiences at university: Tom did a first year of law studies before deciding to study mathematics, while Franck studied two years of "computer science and networks". We can assume that the influence of secondary school was less important for them, as they had previous experiences at university.

CONCLUSIONS

The changes in resources (for teachers and for students), and in the use of these resources, at the secondary-tertiary transition have been under-researched. We contend that the study of "resource use" is an important theme for research, likely to deepen our understandings of teaching and learning processes (initiated or supported by resources) at the beginning of university. In the two case studies presented here we observe that the institution provides the students with numerous resources, mainly mathematical texts. According to the teachers, the epistemic mediation of these resources should support students transiting from school to university mathematics, both in their ways of learning mathematics (more self-regulated work, more autonomous reading of mathematical texts, see e.g. [START_REF] Farah | Students" personal work in mathematics in business school preparatory classes[END_REF], and in their ways of "doing" mathematical work, so that it would become similar to the work of a "real mathematician". However, asking the students about their actual use of resources led to a different picture. The learning at university seemed to be based on listening to the teacher (in lecture), writing down notes, trying similar worked examples, reading the polycopie for exam preparation (in France)in other words an alignment based on a kind of apprenticeship learning. We contend that, based on the two cases we studied, the pragmatic mediation of resources took over the epistemic aspect, at least in the first year. Students used worked examples and lecture notes in order to produce the desired results. At the level of mathematical content, in our case number theory, we detected a potential epistemic aspect in the use of worked examples and lecture notes, when a significant adaptation of a given method was needed. From our study we claim that the "enculturation" and "alignment" processes associated with the change from school to university mathematics education take longer than expected (by university staff), and more awareness and didactical flexibility (from the side of university staff) might help students to bridge this gap more successfully.

NOTES

1. TransMaths project, University of Manchester: http://www.transmaths.org 2. http://braise.univ-rennes1.fr/braise.cgi

Figure 1 .

 1 Figure 1. Resource mediations of students' work with mathematics.

Figure 2 .

 2 Figure 2. Exercise given as homework (Let n be a positive integer, prove that 2n+3 and n 2 +3n+2 are coprime).

Acknowledgement

The second author of this paper recognizes the contribution made by the TransMaths team in the collection of data, the design of instruments and the project, and discussions involving analyses and interpretations of the results. She would also like to acknowledge the support of the ESRC-TLRP award RES-139-25-0241, and continuing support from ESRC-TransMaths award(s) RES-139-25-0241 and RES-000-22-2890.


Sébastien Loisel
email: s.loisel@hw.ac.uk

Hieu Nguyen
email: hnguyen@cimne.upc.edu

An Optimal Schwarz Preconditioner for a Class of Parallel Adaptive Finite Elements

Keywords: Domain decomposition, preconditioner, Bank-Holst paradigm, two-grid discretizations, parallel adaptivity 2010 MSC: 65N55, 65N22, 65F08

A Schwarz-type preconditioner is formulated for a class of parallel adaptive finite elements where the local meshes cover the whole domain. With this preconditioner, the convergence rate of Krylov methods is shown to depend only on the ratio of the second largest and smallest eigenvalues of the preconditioned system. These eigenvalues can be bounded independently of the mesh sizes and the number of subdomains, which proves the proposed preconditioner is optimal. Numerical results are provided to support the theoretical findings.

Introduction

Adaptive finite element method (AFEM) has been a very popular method for solving partial differential equations in science and engineering [START_REF]Accuracy estimates and adaptive refinements in finite element computations[END_REF]. AFEM automatically refines or coarsens meshes to adapt to the computed solutions, thus offering great reliability, robustness and efficiency. Recently, there has been a great demand to use AFEM on parallel distributed supercomputers with many processors to tackle large-scale problems. In order to improve the scalability of AFEM on supercomputers, it is usually combined with a domain decomposition method (DDM). In DDM, the domain is partitioned into a number of subdomains and smaller problems on these subdomains are solved in parallel to determine the overall solution [START_REF] Quarteroni | Domain decomposition methods for partial differential equations[END_REF][START_REF] Toselli | Domain decomposition methods-algorithms and theory[END_REF].

Combining AFEM with DDM, however, introduces challenges that are not present in the traditional version of AFEM. One of the notable challenges is that AFEM builds its meshes gradually and global or near-neighbour information is usually needed. The information can be approximated solutions, error estimates on intermediate meshes or mesh information utilised in adaptive meshing procedures. Since communication costs are high on distributed supercomputers, one wants to avoid communicating as much as possible. This can be achieved when each processor has a mesh of the whole domain and its adaptive enrichment is performed almost independently with those of other processors. In general, the adaptive enrichment on each processor focus mainly on its subdomain. Consequently, after the adaptive enrichment phase, each processor has a composite mesh of the whole domain, which is fine in its subdomain and much coarser elsewhere. The final global mesh is the union of the refined submesh provided by each processor. Figure 1 shows an example of the meshes before and after adaptive enrichment, and the final global mesh.

The initial idea of using local meshes of the whole domain was first introduced by Mitchell for a parallel multigrid method [START_REF] Mitchell | The full domain partition approach to distributing adaptive grids[END_REF]. Then it was further developed into parallel adaptive algorithms. The notable ones include the Bank-Holst algorithm [START_REF] Bank | A new paradigm for parallel adaptive meshing algorithms[END_REF][START_REF] Bank | A new paradigm for parallel adaptive meshing algorithms[END_REF] and the local and parallel algorithms based on two-grid discretizations [START_REF] Xu | Local and parallel finite element algorithms based on two-grid discretizations[END_REF][START_REF] Xu | Local and parallel finite element algorithms based on two-grid discretizations for nonlinear problems[END_REF][START_REF] He | Local and parallel finite element algorithms for the Navier-Stokes problem[END_REF]. Several Figure 1: A coarse mesh with its partition (left), a local mesh on a processor after adaptive enrichment (middle), and the global fine mesh.

variants of these algorithms are studied in [START_REF] Bank | A new parallel domain decomposition method for the adaptive finite element solution of elliptic partial differential equations[END_REF][START_REF] Bank | Some variants of the Bank-Holst parallel adaptive meshing paradigm[END_REF][START_REF] Vey | Adaptive full domain covering meshes for parallel finite element computations[END_REF][START_REF] Bi | Local and parallel finite element discretizations for eigenvalue problems[END_REF][START_REF] Zheng | Local and Parallel Finite Element Algorithm Based on the Partition of Unity for Incompressible Flows[END_REF]. The two algorithms and their variants have been demonstrated to work well for many problems in both science and engineering [START_REF] Bank | A new paradigm for parallel adaptive meshing algorithms[END_REF][START_REF] Mitchell | Adaptive grid refinement and multigrid on cluster computers[END_REF][START_REF] Baker | The adaptive multilevel finite element solution of the poisson-boltzmann equation on massively parallel computers[END_REF][START_REF] Baker | Electrostatics of nanosystems: application to microtubules and the ribosome[END_REF][START_REF] Bank | A new paradigm for parallel adaptive meshing algorithms[END_REF][START_REF] Baker | Poisson-boltzmann methods for biomolecular electrostatics[END_REF][START_REF] Baker | Implicit solvent electrostatics in biomolecular simulation[END_REF][START_REF] Vey | Adaptive full domain covering meshes for parallel finite element computations[END_REF][START_REF] Bank | Domain decomposition and hp-adaptive finite elements[END_REF][START_REF] Shang | Parallel finite element algorithm based on full domain partition for stationary stokes equations[END_REF][START_REF] Bank | A parallel hp-adaptive finite element method[END_REF][START_REF] Shang | A parallel finite element variational multiscale method based on fully overlapping domain decomposition for incompressible flows[END_REF].

Different components contribute to their success. For discussions on how to obtain a suitable partition, where each subdomain contributes roughly the same amount of error, we refer to [START_REF] Bank | A new paradigm for parallel adaptive meshing algorithms[END_REF][START_REF] Bank | A new paradigm for parallel adaptive meshing algorithms[END_REF]. For how to regularise the local meshes to make the global fine mesh conforming, we refer the readers to [START_REF] Bank | Mesh regularization in Bank-Holst parallel hp-adaptive meshing[END_REF]. In this paper, we focus on solving the final global linear system. There is no restriction in the type of solvers can be used. However, it would be ideal if the solver can take advantage of the special formulation of the algorithms. In [START_REF] Bank | A domain decomposition solver for a parallel adaptive meshing paradigm[END_REF], Bank and Lu developed a dedicated domain decomposition solver for the Bank-Holst algorithm. The solver is empirically shown to be robust and efficient for many problems [START_REF] Bank | A new paradigm for parallel adaptive meshing algorithms[END_REF][START_REF] Bank | A domain decomposition solver for a parallel adaptive meshing paradigm[END_REF][START_REF] Bank | Domain decomposition and hp-adaptive finite elements[END_REF][START_REF] Bank | A parallel hp-adaptive finite element method[END_REF]. However, its theoretical convergence can only be fully analysed for a special case where the global interface system is completely presented on all processors [START_REF] Bank | Convergence analysis of a domain decomposition paradigm[END_REF]. For this to happen, all elements attached to the interface, including ones that are far away from the considered subdomain, are required to be refined to the same level of the corresponding elements in the global fine mesh. In addition, the global iteration matrix of the solver is not symmetric, even if all of the local matrices are symmetric. Consequently, conjugate gradient acceleration can not be used.

In this paper, we propose a novel Additive Schwarz (AS) preconditioner that can be combined with Krylov methods, such as CG, to efficiently solve the global linear system in these parallel adaptive algorithms. Our preconditioner is formulated using the local meshes after adaptive enrichment. We recall that these are meshes of the whole domain. They are fine and identical with the global fine mesh in their corresponding subdomains, but generally much coarser elsewhere. If the adaptive meshes are nested, all the finite element spaces associated with the local meshes contain the coarse space associated with the starting coarse mesh. Therefore, there is no need to explicitly add a coarse space as in the traditional two-level AS. However, having the coarse space contained in every subspace introduces the number of subdomains as the largest eigenvalue, which might damages the scability of the preconditioner. Fortunately, we can show that this largest eigenvalue is isolated and the convergence rate of the CG method can be bounded by a quantity that depends only on the ratio of the second largest eigenvalue and the smallest eigenvalue. The ratio is called the effective condition number. Our main theoretical results lies in the analysis of these eigenvalues.

The estimate for the second largest eigenvalue is obtained by establishing a comparison to the largest eigenvalue in a related AS method. Our estimate takes advantage of the strengthened Cauchy-Schwarz inequality for the hierarchical decomposition of local subspaces into a low frequency component and a high frequency component. For estimating the smallest eigenvalue, we follow the subspace correction framework proposed by Xu [START_REF] Xu | Iterative methods by space decomposition and subspace correction[END_REF] and prove the existence of a stable decomposition associated with the local meshes. Since these meshes are generally very different from one another and with the global fine mesh outside of their associated subdomains, the classical analysis of AS method (cf. [START_REF] Dryja | Domain decomposition algorithms with small overlap[END_REF][START_REF] Toselli | Domain decomposition methods-algorithms and theory[END_REF]) does not apply. Our analysis requires new sophisticated interpolation operators based on the work of Scott and Zhang [START_REF] Scott | Finite element interpolation of nonsmooth functions satisfying boundary conditions[END_REF]. These operators are defined in conjunction with a colouring scheme in order to construct the stable decomposition recursively.

In case exact solvers are employed on all local subspaces, our analysis of the eigenvalues shows that the effective condition number of the preconditioned system does not depend on the coarse mesh size H, the fine mesh size h and the number of subdomains N; thus our method is optimal. Roughly speaking, the proposed method performs comparable to a traditional AS method with an extremely thick overlap (δ ≈ H). With proper programming, it delivers superior rate of convergence while demanding about the same amount of computation as with traditional AS methods with a small overlap.

In some aspects, our result is related to the work of Bank et al. [START_REF] Bank | A weakly overlapping domain decomposition preconditioner for the finite element solution of elliptic partial differential equations[END_REF]. However, our preconditioner is very different as we use local subspaces associated with meshes of the whole domain and there is no explicit coarse component.

The rest of this paper is organised as follows. We first state the model problem and introduce key notations in section 2. The formulation of the preconditioner is presented in section 3. The analysis of the convergence of the CG method applied to the preconditioned system, as well as the estimates for the second largest and smallest eigenvalue are carried out in section 4. In section 5, we present some numerical experiments to verify our theoretical results.

Preliminaries

For simplicity of exposition, we confine our discussions to Poisson's equation with homogeneous Dirichlet condition:

-

∆u(x) = f (x) in Ω, u(x) = 0 on ∂Ω . ( 1
)
Here Ω is a bounded domain with polygonal boundary in R d , d = 2, 3.

Let {Ω i } N i=1 be the subdomains in the partition of Ω. We assume that this is a non-overlapping partition, namely Ω = ∪ N i=1 Ωi and Ω i ∩ Ω j = ∅ if i j. In this study, we will use several finite element meshes. The mesh T H of size H will be the shape regular and conforming coarse mesh provided to each processor at the beginning. We further assume that each Ω i is a union of elements in T H . The meshes T i , 1 ≤ i ≤ N are local meshes on each processor at the end of the adaptive enrichment phase . They are meshes of the whole domain which are fine with elements of size h H within Ω i , but coarser and largely coincide with T H elsewhere. The mesh T i is required to be conforming inside Ωi . However, it can have hanging nodes outside of Ωi . In addition, we assume that T i are aligned along their fine interface, namely if Ω i and Ω j are neighbouring subdomains then T i and T j are matched along the part of interface sharing between Ω i and Ω j .

Denote T h the union of T i restricted on Ωi :

T h = ∪ N i=1 (T i | Ωi )
. This mesh is the globally refined, shape regular and conforming mesh of size h of Ω. We assume the following nesting property holds

T H ⊂ T i ⊂ T h , for 1 ≤ i ≤ N.
Now, we extend each Ω i to a larger region Ω † i so that all elements of T i that are outside of Ω † i belong to T H (i.e. there is no refinement in T i outside of Ω † i ). We also require that ∂Ω † i does not cut through any elements in T h or any elements in T i . The extension can be obtained by repeatedly adding to Ω i layers of elements in T i . Since the adaptive meshing on processor i mainly focuses on the inside of the subdomain Ω i , we can assume that only few layers of elements in T H outside of Ω i get refined in creating T i . More specifically, we assume that the width of the regions Ω † i \Ω i are of size H (in case there is barely any refinement outside Ω i , some elements in T H | Ω c i might need to be included in Ω † i ). Figure 2 shows an example of a subdomain Ω i and its extension Ω † i . Lastly, we assume that the (overlapping) partition {Ω † i } N i=1 of Ω can be coloured using at most N c colours, in such a way that if Ω † i and Ω † j are of the same colour and i is different from j, then Ω † i ∩ Ω † j = ∅. Let V 0 , V i , and V h be the linear finite element spaces (of piecewise linear polynomials) associated with T H , T i and T h respectively, i.e.

V 0 = {u H (x) ∈ H 1 0 (Ω)| u H (x)| T ∈ P 1 (T ), ∀T ∈ T H }, V i = {u h (x) ∈ H 1 0 (Ω)| u h (x)| T ∈ P 1 (T ), ∀T ∈ T i }, V h = {u h (x) ∈ H 1 0 (Ω)| u h (x)| T ∈ P 1 (T ), ∀T ∈ T h }.
where P 1 (T ) is the set of linear polynomials defined on element T . Also let {ψ j (x)} n j=1 and {ψ (i) j (x)} n i j=1 be the sets of linear nodal basis function associated with T h and T i , i = 0, 1, . . . , N. Correspondingly, denote {x j } n j=1 and {x (i) j } n i j=1 be the sets of nodal points of T h and T i , i = 0, 1, . . . , N. Here, for convenience, we use T 0 to refer to T H .

The finite element approximation u h (x) ∈ V h of u(x) is the solution of the following problem: find

u h (x) ∈ V h such that a(u h , v h ) = Ω f (x) v h (x) dx, for all v h (x) ∈ V h , (2)
where a(u h , v h ) = Ω (∇u h • ∇v h )dx. For u h (x) ∈ V h , denote u ∈ R n its coordinate vector, i.e., u h (x) = n j=1 u( j) ψ j (x). Then the problem (2) becomes

Au = f, (3)
where A ∈ R n×n , A(k, j) = a(ψ j , ψ k ), and

f ∈ R n , f (k) = Ω f (x) ψ k (x) dx.
Clearly, A is symmetric positive definite and a(u h , v h ) = v T Au = . . (u, v) A .

Preconditioner formulation

We define R T i ∈ R n×n i as follows

R T i =                    ψ (i) 1 (x 1 ) ψ (i) 2 (x 1 ) • • • ψ (i) n i (x 1 ) ψ (i) 1 (x 2 ) ψ (i) 2 (x 2 ) • • • ψ (i) n i (x 2 ) . . . . . . • • • . . . ψ (i) 1 (x n ) ψ (i) 2 (x n ) • • • ψ (i) n i (x n )                    . (4)
We note that R T i is the matrix representation of the point-wise interpolation operator from V i , a coarser mesh with the basis (ψ (i) 1 (x), . . . , ψ (i) n i (x)), to V h , the fine mesh with the basis (ψ 1 (x), . . . , ψ n (x)). Unlike the traditional AS method, the matrix R T i does not consist of just 0 and 1 entries. For the columns associated with the nodal points outside Ω i , there could be multiple nonzero entries belong to (0, 1). However, for other columns (the majority), there is only one nonzero entry [START_REF] Axelsson | On the rate of convergence of the preconditioned conjugate gradient method[END_REF]; and this entry corresponds to a nodal point inside Ω i . Now we introduce the local stiffness matrix A i ∈ R n i ×n i associated with the bilinear form a(•, •) restricted on the subspace V i , as follows

A i (k, j) = a(ψ (i) j , ψ (i) k ) = a         n l 1 =1 R T i (l 1 , j)ψ l 1 , n l 2 =1 R T i (l 2 , k)ψ l 2         = n l 2 ,l 1 =1 R i (k, l2)A l 2 ,l 1 R T i (l 1 , j).

This implies that

A i = R i AR T i . (5)
Clearly, A i is symmetric and positive definite.

Next we define P i = R T i A -1 i R i A. Since P i A = AP i and P 2 i = P i , we see that P i is an A-orthogonal projection onto the range of R T i . Since R T i represent the basis functions of V i , cf. ( 4), P i corresponds to a projection operator which is onto V i . Now we define our symmetric positive definite preconditioner

P -1 = N i=1 R T i A -1 i R i .
Then the preconditioned system can be written as

P -1 A = N i=1 P i = N i=1 R T i A -1 i R i A.
Remark 1. Although the formulation of P i and P -1 largely resemble that of the traditional AS methods, we emphasise that there is a fundamental difference in the subspaces V i in use. In the current approach, V i are the finite element spaces associated with local meshes (T i ) of the whole domain Ω; while in traditional AS methods, V i are finite element spaces associated with the fine meshes (T h | Ω † i ) of subdomains (Ω † i ) slightly larger than Ω i (see [34, p. 59]). In addition, in the current approach, the coarse space V 0 is contained in each V i and there is no explicit coarse component in P -1 . For more information about traditional AS methods, we refer the reader to [START_REF] Toselli | Domain decomposition methods-algorithms and theory[END_REF][START_REF] Quarteroni | Domain decomposition methods for partial differential equations[END_REF] and references therein.

Remark 2. An advantage of P -1 over traditional AS preconditioners is the local matrix A i can be assembled locally on each processor. Consequently, the global matrix A does not need to be assembled (to use in [START_REF] Baker | The adaptive multilevel finite element solution of the poisson-boltzmann equation on massively parallel computers[END_REF]). This is valuable in real-life applications where the system size is large. Remark 3. Each restriction matrix R i has more rows than its counterpart in the traditional two-level AS preconditioner P -1

AS associated with the partitioning {Ω † i } N i=1 and the coarse space V 0 . In addition, the rows of R i associated with the coarse degrees of freedom (dofs) outside Ω † i and the corresponding rows of R 0 in P -1 AS are exactly the same. This suggests an efficient way of computing R i as follows. Each processor independently computes rows of R i associated with dofs in Ω † i and part of R 0 associated with its subdomain. Then the complete R i can be obtained after an MPI Alltoall communication that exchanges the information of R 0 . With this implementation, the cost of evaluating R i , i = 1, 2, . . . , N in P -1 is comparable with the cost of computing R i , i = 0, 1, . . . , N in P -1

AS .

The preconditioner P -1 can be used to accelerate Krylov methods in solving the systems (3). Since P -1 and A are both symmetric positive definite the obvious choice is CG, the conjugate gradient method [START_REF] Golub | Matrix computations[END_REF][START_REF] Trefethen | Numerical linear algebra[END_REF].

In the next section, we will study the convergence of the CG method preconditioned by the proposed preconditioner P -1 .

Convergence analysis

In the first phase of our analysis, we will formulate Euclidean orthogonal projections Q i corresponding to P i and study the spectrum of the preconditioned system

P -1 A = N i=1 P i via that of N i=1 Q i . Let φ 1 (x), φ 2 (x), . . . , φ n (x) be an a(•, •)-orthonormal basis of V h . Without loss of generality, we can assume that φ 1 (x), φ 2 (x), . . . , φ n 0 (x) is an a(•, •)-orthonormal basis of V 0 . Denote U =             φ 1 (x 1 ) • • • φ n (x 1 ) . . . • • • . . . φ 1 (x n ) • • • φ n (x n )             , U 0 =             φ 1 (x 1 ) • • • φ n 0 (x 1 ) . . . • • • . . . φ 1 (x n ) • • • φ n 0 (x n )             , It follows that U T AU = I n , U T 0 AU 0 = I n 0 . Lemma 1. Let Q i = U T AP i U = U -1 P i U.
Then Q i is an Euclidean orthogonal projection and it has block diagonal structure Q i = diag(I n 0 , Qi ), where Qi ∈ R (n i -n 0 )×(n i -n 0 ) is also an Euclidean orthogonal projections. In addition,

σ(P -1 A) = σ( N i=1 Q i ) = {N} ∪ σ( N i=1 Qi ). ( 6
)
where σ(•) denotes the spectrum.

Proof. Since Q 2 i = Q i and Q T i = Q i , Q i is an Euclidean orthogonal projection.
In addition, as V 0 ⊂ V i and the columns of U 0 and R T i represent basis functions of V 0 and V i respectively, we see that range(U 0 ) ⊂ range(R T i ) = range(P i ). Therefore, we can write

P i U = P i [U 0 * ] = [P i U 0 * ] = [U 0 * ] and Q i = U T AP i U = U T 0 * A [U 0 * ] = U T 0 AU 0 * * * = I n 0 Z i Z T i Qi . Since Q 2 i = Q i , it implies that Z i Z T i = 0, or Z i = 0. Therefore, Q i = diag(I n 0 , Qi ).
As Q i is an orthogonal Euclidean projection, Qi is also an orthogonal Euclidean projection. The first part of ( 6) follows from the fact that

N i=1 Q i = U -1        N i=1 P i        U = U -1 (P -1 A)U.
The second part of ( 6) is a consequence of

N i=1 Q i = diag(NI n 0 , N i=1 Qi ).
Lemma 2. Let λmin and λmax be the smallest and largest eigenvalues of N i=1 Qi respectively. Then

σ A (P -1 A) ⊂ [ λmin , λmax ] ∪ {N}, where 0 < λmin ≤ λmax ≤ N. (7)
Proof. Since Qi is a projection, σ( Qi ) = {0, 1} and σ( N i=1 Qi ) ⊂ [0, N]. Because P -1 and A are both positive definite, λmin > 0. Then [START_REF] Bank | Hierarchical bases and the finite element method[END_REF] follows from [START_REF] Baker | Electrostatics of nanosystems: application to microtubules and the ribosome[END_REF].

Remark 4. The result presented in [START_REF] Bank | Hierarchical bases and the finite element method[END_REF] indicates that λmin and λmax are actually the smallest and the second largest eigenvalues of the preconditioned system P -1 A. The eigenvalue λmax equals N if and only if the local subspace V i has common subset strictly larger than V 0 . This only happens when N is small and local meshes are structured. In general, N > λmax and N is an isolated eigenvalue of P -1 A.

In the next step, we will take advantage of the special spectrum decomposition in [START_REF] Baker | Electrostatics of nanosystems: application to microtubules and the ribosome[END_REF] to study the convergence of the CG method applied to the preconditioned system P -1 A. But first, we quote from [START_REF] Axelsson | On the rate of convergence of the preconditioned conjugate gradient method[END_REF] the following result

e k A e 0 A = inf q∈P k q(P -1 A)e 0 A e 0 A ≤ inf q∈P k max λ∈σ(P -1 A) |q(λ)|. (8)
Here e k = u ku is the exact error at the step n of the CG method, σ(P -1 A) denotes the spectrum of P -1 A, and P k is the set of polynomials q of degree k or less, with q(0) = 1. More details about the CG method can be found in [START_REF] Trefethen | Numerical linear algebra[END_REF][START_REF] Golub | Matrix computations[END_REF] and the references therein.

Theorem 3. The error of the CG method applied to equation (3) when it is left-preconditioned by P -1 satisfies

e k A e 0 A ≤ 2(N -λmin ) N       √ κ -1 √ κ + 1       k-1 < 2       √ κ -1 √ κ + 1       k-1 , (9)
where κ = λmax / λmin is called the effective condition number of P -1 A.

Proof. By [START_REF] Bank | Some variants of the Bank-Holst parallel adaptive meshing paradigm[END_REF], it is sufficient to find a polynomial q(x) ∈ P k whose maximum value for x ∈ [ λmin , λmax ] is the second quantity in [START_REF] Bank | PLTMG: A Software Package for Solving Elliptic Partial Differential Equations[END_REF]. Consider the polynomial

q(x) = T k-1 (γ -2x λmax -λmin )(N -x) NT k-1 (γ) , (10)
where γ = ( λmax + λmin )/( λmaxλmin ) > 1 and T k-1 (x) is the Chebyshev polynomial of degree k -1. More information about Chebyshev polynomials can be found in [START_REF] Mason | Chebyshev polynomials[END_REF]. Clearly, q has degree k and q(0) = 1. For x ∈ [ λmin , λmax ], the quantity γ -2x λmaxλmin belongs to [-1, 1] and |N -x| ≤ N -λmin . It follows that

T k-1 γ - 2x λmax -λmin (N -x) ≤ N -λmin . ( 11
)
We use the standard estimate for T k-1 (x):

T k-1 (γ) = 1 2               √ κ + 1 √ κ -1       k-1 +       √ κ + 1 √ κ -1       -(k-1)         ≥ 1 2       √ κ + 1 √ κ -1       k-1 . ( 12
)
More details can be found in [35, p. 300]. The inequalities (9) then follow immediately from ( 11) and ( 12).

We have shown in Theorem 3 that the convergence of the CG method with preconditioner P -1 can be bounded by quantities mainly depend on the ratio of λmin and λmax , the second largest and smallest eigenvalues of P -1 A. In the next step, we present estimates for these eigenvalues.

Second largest eigenvalue estimate

Our plan to estimate λmax is to seek an explicit formula for Qi and compare the largest eigenvalue of N i=1 Qi with that of the related traditional AS method. We begin with some preparation.

Let Vi be the subspace of V i spanned by nodal basis functions associated with nodal points which are in T i but are not in T H . With a slight abuse of notation we can write Vi = span ψ (i) j (x), ∀ j s.t x j T H Clearly, V i = V 0 ⊕ Vi . This is a hierarchical decomposition of V i into subspace V 0 of coarse basis functions and subspace Vi of fine basis functions. We quote from [START_REF] Bank | Hierarchical bases and the finite element method[END_REF] (see also [START_REF] Eijkhout | The role of the strengthened Cauchy-Buniakowskiȋ-Schwarz inequality in multilevel methods[END_REF]) the following well-known result of the strengthened Cauchy-Schwarz inequality for hierarchical bases.

Lemma 4. Given the finite element hierarchical decomposition V i = V 0 ⊕ Vi . Then for all v 0 (x) ∈ V 0 and all vi (x) ∈ Vi :

|a(v 0 , vi )| ≤ γ v 0 A vi A , i = 1, . . . , N. (13)
Here the constant γ, 0 < γ < 1, (the maximum of all the constants associated with local meshes T i ) depends on the shape regularity quality of the meshes T H , T i , but is otherwise independent of the mesh sizes h and H.

Now let m i = n i -n 0 and ω (i) 1 (x), • • • , ω (i) m i (x) be an a(•, •)-orthonormal basis of Vi . Denote W i =              ω (i) 1 (x 1 ) • • • ω (i) m i (x 1 ) . . . • • • . . . ω (i) 1 (x n ) • • • ω (i) m i (x n )              .
We note that the columns of U 0 and the columns of W i represent bases of V 0 and Vi respectively. Therefore, range

(P i ) = range(R T i ) = range([U 0 W i ]) since V 0 ⊕ Vi = V i . Lemma 5. Let U T AW i = [X T i Y T i ] T , where X i ∈ R n 0 ×m i , Y i ∈ R n-n 0 ×m i . Then Qi = Y i (Y T i Y i ) -1 Y T i , for i = 1, . . . , N. Proof. Since Q i = U T AP i U and U is non-singular, we have range(Q i ) = U T A(range(P i )) = U T A(range([U 0 W i ])) = range(U T A[U 0 W i ]) = range I X i 0 Y i = range I 0 0 Y i = range(E i ), (14)
where E i = diag(I, Y i ). So Q i is an projection onto the range of E i . In addition,

n i = dim(V i ) = rank([U 0 W i ]) = rank I X i 0 Y i = rank I 0 0 Y i . Therefore, rank(Y i ) = n i -n 0 = m i .
In other words, the matrix Y i has full rank. It follows that the columns of E i are linearly independent. This together with ( 14) imply

Q i = E i (E T i E i ) -1 E T i = I 0 0 Y i (Y T i Y i ) -1 Y T i .
Then the desired equality follows from the fact that Q i = diag(I n 0 , Qi ). Lemma 6. For X i , Y i defined in Lemma 5, we have

(1 -γ 2 )I Y T i Y i , (15)
where 0 < γ < 1 is the constant introduced in Lemma 4. The notation denotes the positive semi-definite ordering (cf. [START_REF] Horn | Matrix analysis[END_REF]). In addition,

N i=1 Y i Y T i N c I n-n 0 . (16)
Proof. Using the definitions of X i , Y i and the fact that W i has A-orthonormal columns, we have

X T i X i + Y T i Y i = [X T i Y T i ] X i Y i = W T i AUU T AW i = W T i AW i = I m i . (17)
Therefore, in order to show (15) we will bound X T i X i from above. For v 0 (x) ∈ V 0 and vi (x) ∈ Vi , their coordinate vectors are of the following forms

v 0 = U y 0 , vi = [U 0 W i ] 0 z , y ∈ R n 0 , z ∈ R m i .
Now the inequality (13) can be written in the matrix form as follows

[y T 0]U T A[U 0 W i ] 0 z ≤ γ [y T 0]U T AU y 0 [0 z T ] U T 0 W T i A[U 0 W i ] 0 z .
Equivalently for any y ∈ R n 0 and z ∈ R

m i : [y T 0] I X i 0 Y i 0 z = y T X i z ≤ γ y 2 z 2 .
This implies that X i 2 ≤ γ and

X T i X i 2 ≤ γ 2 .
In other words, X T i X i γ 2 I m i . Then (15) follows immediately from [START_REF] Bank | A parallel hp-adaptive finite element method[END_REF]. Next we are going to prove [START_REF] Bank | Mesh regularization in Bank-Holst parallel hp-adaptive meshing[END_REF]. Let

V † i = V h | Ω † i , i = 1, .
. . , N. We note that V † i are the local spaces in the related traditional AS method (see [34, p. 59]). Since all elements in T i that are outside of Ω † i belong to T H , Vi is a subset of V † i . Consequently, there is an orthonormal basis of V † i in the form of ω (i) 1 , . . . , ω (i) m i , ω (i) m i +1 , . . . , ω (i) mi . Let W i ∈ R n× m i be defined as follows

W i =               ω (i) 1 (x 1 ) • • • ω (i) m i (x 1 ) . . . • • • . . . ω (i) 1 (x n ) • • • ω (i) m i (x n )               . Denote [ X T i Y T i ] = U T A W i , where X i ∈ R n 0 × m i , Y i ∈ R n-n 0 × m i . Then the first m i columns of Y i form Y i . Assume Y i = [y i 1 • • • y i m i ] and Y i = [y i 1 • • • y i m i y i m i +1 • • • y i m i ]. For any z ∈ R n-n 0 we have z T        N i=1 Y i Y T i        z = N i=1 m i j=1 (y i j T z) 2 ≤ N i=1 m i j=1 (y i j T z) 2 = z T        N i=1 Y i Y T i        z. (18)
Therefore,

N i=1 Y i Y T i N i=1 Y i Y T i . (19)
Now let Q i be the Euclidean orthogonal projection corresponding to the Schwarz projection P i associated with Ω † i in the traditional AS method (see [34, chapter 2]). Similar to ( 14), we have range( Q i ) = range(U T A W i ). In addition,

F i = U T A W i = [ X T i Y T i
] has orthonormal columns. Thus the projection Q i can be written as

Q i = F i F T i = X i X T i X i Y T i Y i X T i Y i Y T i . Therefore, for any z ∈ R n-n 0 z T N i=1 Y i Y T i z = [0 z T ] N i=1 Q i 0 z ≤ ρ( N i=1 Q i ) z T z = ρ( N i=1 P i ) z T z,
where ρ denote the spectral radius. On the other hand, according to [21, Theorem 4.1], ρ(

N i=1 P i ) ≤ N c . Consequently, Y i Y T i N c I n-n 0 . (20)
The ordering [START_REF] Bank | Mesh regularization in Bank-Holst parallel hp-adaptive meshing[END_REF] then follows from [START_REF] Bi | Local and parallel finite element discretizations for eigenvalue problems[END_REF] and [START_REF] Chen | iFEM: an innovative finite element methods package in MATLAB[END_REF].

We now present one of our main results, the estimate for the second largest eigenvalue.

Theorem 7. The second largest eigenvalue of the preconditioned system P -1 A is bounded as follows

λmax ≤ N c (1 -γ 2 ) . (21)
Proof. From (5), we have λmax

= ρ( N i=1 Qi ) = ρ N i=1 Y i (Y T i Y i ) -1 Y T i .
On the other hand, it follows from ( 16) and (15) that

N i=1 Y i (Y T i Y i ) -1 Y T i 1 (1 -γ 2 ) N i=1 Y i Y T i N c (1 -γ 2 ) I n-n 0 .
Then the equality (21) follows immediately.

Smallest eigenvalue estimate

Our estimate of λmin follows the standard approach where a stable decomposition is constructed [START_REF] Xu | Iterative methods by space decomposition and subspace correction[END_REF][START_REF] Dryja | Domain decomposition algorithms with small overlap[END_REF][START_REF] Toselli | Domain decomposition methods-algorithms and theory[END_REF]. However, as the local meshes T i are meshes of the whole domain and they are very different from one another and from the global fine mesh T h outside of their associated subdomains, the stable decomposition in [START_REF] Dryja | Domain decomposition algorithms with small overlap[END_REF][START_REF] Toselli | Domain decomposition methods-algorithms and theory[END_REF] is no longer valid. In order to adapt to the situation, we build our stable decomposition inductively on the colouring defined in section 2. In our construction, the partition of unity is replaced by a set of cut-off functions, and the point-wise interpolation is replaced by a special interpolation inspired by [START_REF] Scott | Finite element interpolation of nonsmooth functions satisfying boundary conditions[END_REF].

Cut-off functions. Denote C k the set of indices of subdomains coloured by colour c k , 1 ≤ c k ≤ N c . Then for each subdomain Ω i , i ∈ C k , we define the cut-off function θ (c k ) i (x) as follows:

θ (c k ) i (x) =              1 if x ∈ Ωi 0 if x Ω † i dist(x,∂Ω † i \∂Ω) dist(x,∂Ω † i \∂Ω)+dist(x,∂Ω i \∂Ω) if x ∈ Ω † i \Ω i , (22)
Clearly, θ (c k ) i is well-defined, continuous on Ω and satisfies

0 ≤ θ (c k ) i (x) ≤ 1, for all x ∈ Ω. ( 23
)
In addition, supp(θ

(c k ) i ) ⊂ Ω † i , supp(θ (c k ) i ) ∩ supp(θ (c k j ) = ∅, i, j ∈ C k , i j. ( 24
)
Since the width of Ω † i \Ω i is of size H, according to [START_REF] Toselli | Domain decomposition methods-algorithms and theory[END_REF]Lemma 3.4], there exists constant C θ does not depend on i and H such that

∇θ (c k ) i ∞ ≤ C θ /H. ( 25
)
In the next step, we present the framework to construct the modified Lagrange type interpolation operator introduced by Scott and Zhang in [START_REF] Scott | Finite element interpolation of nonsmooth functions satisfying boundary conditions[END_REF]. Some stability properties for this type of interpolation will also be provided for later use.

Modified Lagrange interpolations. Let T • be a finite element mesh of Ω with its set of nodal points

N • = {x j • } n • j=1
. Denote V • the finite element space associated with T • and let {ψ • j } n • j=1 be the set of linear nodal basis functions of V • corresponding to N • . For any node x • j , we fix an edge e • j in T • that has x • j as one of its vertex. Let {x • j,k } 2 k=1 be the two nodal points in N • associated with e • j . Without lost of generality, we choose

x • j,1 = x • j . For the nodal basis {ψ • j,k } 2 k=1 associated with {x • j,k } 2 k=1 , we have an L 2 (e • j )-dual basis {η • j,k } 2 k=1 defined by e • j η • j,k ψ • j,l = δ kl , k, l = 1, 2
, where δ k,l is the Kronecker delta. For simplicity, we let η

• j ≡ η • j,1 , for x • j ∈ N i . Then, we have e • j η • j ψ • k = δ jk , k, j = 1, 2, . . . , n • . ( 26
)
Now we can define the interpolation operator,

I • = I {e • j } T • : H 1 (Ω) → V • , I • u(x) = n i j=1 ψ • j (x) e • j η • j (ξ)u(ξ) dξ. (27)
Here, the notation

I {e • j }
T • is used to emphasise that the interpolation operator depends on the mesh T • and the choice of edges {e • j } n • j=1 . However, for simplicity I • is used in other places. The following Lemma is useful when we want to consider I • u on a subset of Ω. Lemma 8. Let u be a function in H 1 (Ω) and Ω s be a subset of Ω. Assume that Ω s is also an union of elements in T • . Then following statement holds

I • u(x) = j, x • j ∈ Ωs ψ • j (x) e • j η • j (ξ)u(ξ) dξ, for all x ∈ Ωs .
Proof. The proof is obvious as the basis functions ψ • j (x) associated with x • j Ωs vanish in Ωs .

Let {x (i) j } n i j=1 be the set of nodal points of the finite element mesh T i , 0 ≤ i ≤ N. For each mesh T i , 0 ≤ i ≤ N we will choose a set of edges {e (i) j } n i j=1 in T i corresponding to {x (i) j } n i j=1 that satisfies the following conditions: 10

(i) e (i) j contains x (i) j (ii) e (i) j ∈ ∂Ω, if x (i) j ∈ ∂Ω (iii) e (i) j ∈ ∂Ω i \∂Ω, if x (i) j ∈ ∂Ω i \∂Ω, i 0 (iv) e (i) j ∈ ∂Ω k , if x (i) j
∂Ω ∪ ∂Ω i is shared by two or more subdomains in the partition {Ω l } N l=1 .

Here Ω k is the subdomain with smallest colour that contains x (i) j .

For each mesh T i , we fix a choice of edges {e (i) j } n i j=1 satisfying the four conditions above. Then we let

I h,H i = I {e (i) j } T i : H 1 (Ω) → V i , 1 ≤ i ≤ N I H = I {e (0) j } T 0 : H 1 (Ω) → V 0 ,
be the modified Lagrange interpolation operators associate with T i and {e (i) j } n i j=1 , and with T 0 and {e (0) j } n 0 j=1 respectively. According to [START_REF] Scott | Finite element interpolation of nonsmooth functions satisfying boundary conditions[END_REF], there exist a constant C I depend only on the shape regularity of the associated meshes such that

I h,H i u H 1 (K) ≤ C I |u| H 1 (ω K ) , K, ω K ∈ T i , (28)
u -I H u L 2 (K) ≤ C I H|u| H 1 (ω K ) , K, ω K ∈ T H , (29)
I H u H 1 (K) ≤ C I |u| H 1 (ω K ) , K, ω K ∈ T H . ( 30
)
where

ω K = interior { K j | K j ∩ K ∅, K i ∈ T • } .
Lemma 9. The interpolation operator I h,H i preserves fine functions in the regions where the mesh T i is fine. In other words, I h,H i u| Ωi = u| Ωi , for any function u(x) satisfies u(x)

| Ωi ∈ V h | Ωi . Proof. Let x (i) j be a nodal point of T i , x (i) j ∈ Ωi . Since T i | Ω i ≡ T h | Ω i ,
this nodal point also presents in T h . In addition, the two nodal basis functions associated with x (i) j in V i and V h are identical on Ωi , namely

ψ (i) j | Ω i = ψ j i | Ω i . (31)
On the other hand, by (iii) the chosen edge e (i) j ∈ T i for the nodal point x (i) j should also be an edge in T h if x (i) j ∈ Ωi . Therefore, by [START_REF] Karypis | A fast and high quality multilevel scheme for partitioning irregular graphs[END_REF] we have

e (i) j η j (ξ) u(ξ) dξ = u(x j ), for all x (i) j ∈ Ωi . (32)
Using ( 27), Lemma 8, ( 32) and ( 31), we have

I h,H i u(x) = n i j=1 ψ (i) j (x) e (i) j η (i) j (ξ)u(ξ) dξ = j, x j ∈ Ωi ψ (i) j (x) e (i) j η (i) j (ξ)u(ξ) dξ = j, x j ∈ Ωi ψ (i) j (x) u(x j ) = u(x).
We are now in a position to estimate the smallest eigenvalue of the preconditioned system P -1 A. The idea is to construct local functions colour by colour. The proposed interpolations will ensure that residual functions vanish on all considered subdomains, and stay zero there in later induction steps. The following Lemma lays the foundation for our construction of local functions in a stable decomposition. Lemma 10. Assume u(x) ∈ V h . Let u (0) (x) := u(x). Then our inductive construction of residual functions u (k) (x) is as follows

w (k) = I H u (k-1) , (w (k) ∈ V H ) (33)
v (k) = u (k-1) -w (k) , (v (k) ∈ V h ) (34)
v (k) i = I h,H i θ (c k ) i v (k) , (v (k) i ∈ V i ). (35)
u (k) = v (k) - i∈C k v (k) i = v (k) - i∈C k I h,H i θ (c k ) i v (k) , (u (k) ∈ V h ) (36)
where k = 1, 2, . . . , N c . Then the following equalities hold

u (k) | Ωi ≡ 0, for all i ∈ C k i , k i ≤ k, (37) u
= N c -1 k=0 w (k) + N c k=1 i∈C k v (k) i , (38)
i∈C k v (k) i 2 H 1 (Ω) = i∈C k v (k) i 2 H 1 (Ω) . (39)
Proof. Substituting k = 1 into (36) gives u (1) = v (1) -i∈C 1 I h,H i θ (c 1 ) i v (1) . For i, j ∈ C 1 , i j, according to [START_REF] Eijkhout | The role of the strengthened Cauchy-Buniakowskiȋ-Schwarz inequality in multilevel methods[END_REF], θ (c 1 ) i = 1 on Ωi , and θ (c 1 ) j = 0 on Ωi . Therefore, I h,H i θ (c 1 ) i v (1) = I h,H i v (1) = v (1) on Ωi , i ∈ C 1 as a consequence of Lemma 9. In addition, I h,H j θ (c 1 ) j v (1) ≡ I h,H j 0 = 0 on Ωi . Combining these together, we have

u (1) | Ωi ≡ 0, for all i ∈ C 1 . (40)
For any x ∈ Ωi , i ∈ C 1 from [START_REF] Shang | Parallel finite element algorithm based on full domain partition for stationary stokes equations[END_REF] and Lemma 8, it follows that

w (2) (x) = I H u (1) (x) = j, x (0) j ∈ Ωi ψ (0) j (x) e (0) j η (0) j (ξ) u (1) (ξ) dξ (41)
By condition (iv), e (0) j ∈ Ωi for all x (0) j ∈ Ωi , i ∈ C 1 . This together with [START_REF] Zheng | Local and Parallel Finite Element Algorithm Based on the Partition of Unity for Incompressible Flows[END_REF] imply

w (2) | Ωi ≡ 0, for all i ∈ C 1 . (42)
Then from ( 34), ( 40) and (42), it follows that

v (2) | Ωi ≡ 0, for all i ∈ C 1 . (43)
Substituting k = 2 into (36), we obtain (2) . Similarly, we have

u (2) = v (2) -i∈C 2 I h,H i θ (c 2 ) i v
u (2) | Ωi ≡ 0, for all i ∈ C 2 . (44)
Now assume l ∈ C 1 . For any x ∈ Ωl , i ∈ C 2 according to Lemma 8,

I h,H i θ (c 2 ) i v (2) (x) = j, x (i) j ∈ Ωl ψ (i) j (x) e (i) j η (i) j (ξ)(θ (c 2 ) i v (2) )(ξ) dξ. (45)
On the right hand side of (45), if x (i) j ∈ Ωl \∂Ω i then by condition (iv), e (i) j ∈ ∂Ω l ⊂ Ωl . This together with (43) imply 26), ( 22), (43) and the fact that x (i) j ∈ Ωl , we have e (i)

e (i) j η (i) j (ξ)(θ (c 2 ) i v (2) )(ξ) dξ = 0. If x (i) j ∈ Ωl ∩ ∂Ω i then by condition (iii), e (i) j ∈ ∂Ω i . From (
j η (i) j (ξ)(θ (c 2 ) i v (2) )(ξ) dξ = θ (c 2 ) i v (2) (x (i) j ) = v (2) (x (i) j ) = 0. In summary, I h,H i θ (c 2 ) i v (2) = 0 on Ωl , for all l ∈ C 1 , i ∈ C 2 .
This together with (43) imply u (2) | Ωl ≡ 0, for all l ∈ C 1 . From (44), it follows that

u (2) | Ωi ≡ 0, for all i ∈ C 1 ∪ C 2 .
Continuing this process for k = 3, . . . , N c , we obtain [START_REF] Xu | Iterative methods by space decomposition and subspace correction[END_REF].

Since { Ωi } N i=1 covers Ω, (37) implies u (N c ) | Ω ≡ 0. Tracing backward, we have

0 = u (N c ) = u (N c -1) -w (N c ) - i∈C N c v (N c ) i = u (N c -2) -w (N c -1) -w (N c ) - i∈C N c -1 v (N c -1) i - i∈C N c v (N c ) i = u (0) - N c k=1 w (k) - N c k=1 i∈C k v (k) i .
This implies [START_REF] Xu | Local and parallel finite element algorithms based on two-grid discretizations[END_REF] because

u (0) (x) = u(x). Since θ (c k ) i has support on Ω † i , the functions θ (c k ) i v (k) and consequently v (k) i = I h,H i θ (c k ) i v (k) also have support on Ω † i . Therefore, v (k)
i have disjoint supports, and (39) follows immediately. Now we are ready to state the main result of this subsection.

Theorem 11. For any u(x) ∈ V h there exists a decomposition

u = N i=1 u i , u i (x) ∈ V i , 1 ≤ i ≤ N, that satisfies N i=1 a(u i , u i ) ≤ C m a(u, u),
where C m is a constant independent of H, h and N but not N c . In addition, the smallest eigenvalue of the preconditioned system P -1 A can be bounded from below as follows

λmin ≥ C -1 m .
Proof. In this proof, for simplicity, we use x y to denote x ≤ C y, where the constant C might depend on the interpolation constant, the constant in bounding the gradients of cut-off functions and the number of colours in the colouring (C I , C θ and N c respectively) but does not depend on the mesh sizes (h, H) and the number of subdomains in the partition (N).

Based on [START_REF] Xu | Local and parallel finite element algorithms based on two-grid discretizations[END_REF] in Lemma 10, we define

u = N i=1 u i , where u i = w (k i ) + v (k i ) i , if i = min(C k i ) v (k i ) i , otherwise . (46)
We will show that this is a stable decomposition. First, from the definition of w (k) in [START_REF] Shang | Parallel finite element algorithm based on full domain partition for stationary stokes equations[END_REF] and the stability properties of I H in [START_REF] Quarteroni | Domain decomposition methods for partial differential equations[END_REF], it follows that |w (k) | H 1 (K) ≤ C I |u (k-1) | H 1 (ω K ) , for K and ω K ∈ T 0 . Squaring and summing over all K ∈ T 0 , we have

|w (k) | 2 H 1 (Ω) |u (k-1) | 2 H 1 (Ω) . (47)
Then it follows from (34), Young's inequality, and (47) that

|v (k) | 2 H 1 (Ω) ≤ 2 |u (k-1) | 2 H 1 (Ω) + |w (k) | 2 H 1 (Ω) |u (k-1) | H 1 (Ω) . (48)
On the other hand, from ( 34), ( 33) and ( 29), we have

v (k) L 2 (K) = u (k-1) -I H u (k-1) L 2 (K) ≤ C I H |u (k-1) | H 1 (ω K ) , K, ω K ∈ T 0 .
Squaring and summing over all K ∈ T 0 , we obtain

v (k) 2 L 2 (Ω) H 2 |u (k-1) | 2 H 1 (Ω) . (49)
For i ∈ C k , from ( 35) and ( 28) it follows that

|v (k) i | H 1 (K) = |I h,H i (θ (c k ) i v (k) )| H 1 (K) ≤ C I |θ (c k ) i v (k) | H 1 (K) , K, K ∈ T i . (50)
Squaring and summing over all K ∈ T i , we find that

|v (k) i | 2 H 1 (Ω) |θ (c k ) i v (k) | 2 H 1 (Ω) . (51)
For 1 ≤ k ≤ N c , using ( 39), (51) and Young's inequality, we have

i∈C k v (k) i 2 H 1 (Ω) = i∈C k v (k) i v (k) 2 dx H -2 v (k) L 2 (Ω) |v (k) | 2 H 1 (Ω) . (54)
Combining ( 52) and ( 53) and (54), we have

i∈C k v (k) i 2 H 1 (Ω) |v (k) | 2 H 1 (Ω) . (55)
Using ( 36), Young's inequality, (55) and (48), it yields

|u (k) | 2 H 1 (Ω) = v (k) - i∈C k v (k) i 2 H 1 (Ω) ≤ 2          |v (k) | 2 H 1 (Ω) + i∈C k v (k) i 2 H 1 (Ω)          |v (k) | 2 H 1 (Ω) ) |u (k-1) | 2 H 1 (Ω) .
Consequently,

|u (k) | 2 H 1 (Ω) |u (0) | 2 H 1 (Ω) = |u| 2 H 1 (Ω) . (56)
Using (46), Young's inequality, (47), ( 39), ( 55) and (48), we have

N i=1 a(u i , u i ) = N c k=1 i∈C k |u (k) i | 2 H 1 (Ω) ≤ 2 N c k=1         |w (k) | 2 H 1 (Ω) + i∈C k |v (k) i | 2 H 1 (Ω)         |u (k-1) | 2 H 1 (Ω) . (57)
Then it follows from (57) and ( 56) that there exist C m independent of h, H and N such that

N i=1 a(u i , u i ) ≤ C m |u| 2 H 1 (Ω) = C m a(u, u). (58)
The lower bound for the smallest eigenvalue λmin is followed immediately by [START_REF] Xu | Iterative methods by space decomposition and subspace correction[END_REF] (see also [START_REF] Toselli | Domain decomposition methods-algorithms and theory[END_REF]Chapter 2]).

Combining Theorems 7 and 11, we find a bound for the effective condition number of the proposed method.

Theorem 12. In case exact solvers are employed on all subspaces, the effective condition number of the preconditioned system P -1 A satisfies

κ = λmax λmin ≤ C m N c
(1 -γ 2 ) .

Numerical Experiments

In this section, we present two numerical experiments to support the theory formulated in section 4. A vectorised Matlab code which allows hanging nodes is developed for this study. The finite element codes iFEM [START_REF] Chen | iFEM: an innovative finite element methods package in MATLAB[END_REF] and PLTMG [START_REF] Bank | PLTMG: A Software Package for Solving Elliptic Partial Differential Equations[END_REF] are also used extensively in early testing.

L-shaped Domain

In this experiment, we consider the problem described in (1), where Ω is the L-shaped domain obtained from the unit square by removing the lower right quarter (see Figure 3). We will study the changes of λmax and λmin when h, H and N vary. According to Theorem 7 and Theorem 11, we expect λmax and λmin do not depend on h and H, but weakly depend on N.

By serial adaptivity, we create a conforming triangular mesh of 293 elements and 129 vertices. The mesh is partitioned into N = 4, 8, . . . , 64 subdomains using METIS [START_REF] Karypis | A fast and high quality multilevel scheme for partitioning irregular graphs[END_REF]. Then, we perform L = 0, 1, 2 globally uniform refinements to create coarse meshes of different sizes (different H). These coarse meshes of the whole domain are then broadcast to N processors where they are adaptively refined by l = 1, 2, 3 cycles of adaptive refinements (vary h) in parallel. The adaptive refinement on each processor focuses on the associated local subdomain. However, there might be refinement outside to keep the final mesh on each processor conforming across the interface with the local meshes in the neighbouring subdomains . The global fine mesh is the union of the refined submeshes provided by all processors. The meshes at different stages of the experiment for L = 0, N = 4 and l = 2 is shown in Figure 3. .033 6.035 6.035 6.000 6.000 6.000 6.000 6.000 6.000

L = 0 L = 1 L = 2 l = 1 l = 2 l = 3 l = 1 l = 2 l = 3 l = 1 l = 2 l = 3 N =
From Table 1, we can see that there is little or no change in λmin when N and H (effectively L) vary. When h (effectively l) varies, there are changes in λmin . However, these changes are not significant and we can safely say that λmin is bounded independently of N, H and h.

There are almost no change in λmax when H and h (effectively L and l ) vary especially when the coarse meshes are sufficiently fine (L = 1 and L = 2). We do see that λmax increase consistently as N increases. However, the increase is modest and is at most proportional to the number of color N c which is much smaller than the number of subdomain N when N is sufficiently large.

In conclusion, the behavior of λmax and λmin in this experiment agrees with the estimates in Theorem 7 and Theorem 11.

Seepage Under Dam

In the second experiment, we study seepage under a dam. The problem is modeled as the stationary state of groundwater flowing through porous media, which has the following governing equation:

-∇ • (k(x, y)∇h(x, y)) = 0 in Ω, h = g D on ∂ D Ω, ∂h ∂n = g N on ∂ N Ω,
where h(x, y) is the total hydraulic head and k(x, y) is the hydraulic permeability coefficient. Here, we assume the hydraulic head is constant across the z direction and only work with two dimensional space. 13) 13( 13) 12( 16) 12( 14) 13( 13) 13( 15) 13 [START_REF] Bank | A parallel hp-adaptive finite element method[END_REF] The simulation domain Ω, which is under the dam (in solid color), is illustrated in Figure 4. The upstream and downstream water level is assumed to be 10 and 1, respectively. This implies the Dirichlet boundary condition h| D 1 = g D1 = 10 and h| D 2 = g D2 = 1. In addition, we assume that the dam is made of impermeable material and there is no flow coming through the bottom, the left, the right boundary of the domain. Therefore, zero Neumann condition (∂h/∂n = g N = 0) is imposed on associated boundary components. In our experiment, k = 10 -5 .

We will study the convergence of the CG method in solving (3) with the proposed preconditioner P -1 . According to Theorem 3 and Theorem 12, we expect that the number of iterations required to reduced the residual below a fixed relative tolerance does not depend on the mesh sizes (H, h) and the number of subdomains (N) but on the number of colours (N c ).

Our construction of the experiment is similar to that of the first experiment. We create, by serial adaptivity, two unstructured conforming triangular meshes of n 0 = 608 and n 0 = 1042 vertices. These two coarse meshes, which has different mesh sizes (different H), are partitioned into N = 4, 8, . . . , 64 subdomains. For each combination of meshes and partitions, we apply l = 1, 2, 3, 4 levels of refinement locally on each subdomain to create local adaptive meshes of the whole domain. These local meshes are used to formulate the proposed preconditioner P -1 . The traditional two-level AS preconditioner P -1

AS with the minimal overlap (δ = h) is also formulated for comparison. Table 2 reports the number of CG iterations required to reduce the residual by a factor of 10 6 using P -1 and P -1 AS (in parentheses). Except for a few cases where the two preconditioners require the same number of iterations, P -1 clearly outperforms P -1 AS , especially for large problems (large number of refinements l). With P -1 , the iteration number barely changes when l (effectively h) or n 0 (effectively H) vary. However, when l increases the overlap in P -1 AS (δ = h) decreases while the size of the subdomains remains the same. As the conditioned number with the two-level AS is proportional to (1 + H/δ) [START_REF] Dryja | Domain decomposition algorithms with small overlap[END_REF][START_REF] Toselli | Domain decomposition methods-algorithms and theory[END_REF], we see increase in the iteration number associated with P -1 AS when l increases. In order for P -1

AS to be competitive with P -1 , the overlap δ need to be at least l layers of elements. This implies more computational and communication cost associated with the overlap when l increases.

For both preconditioners, the iteration number increases as N increases. However, the increase is modest and is at most proportional to N c , the number of colours.

This experiment clearly demonstrates that our preconditioner is more efficient than the traditional two-level AS preconditioner, especially for large problems requiring many levels of refinement. The experiment also confirms that the performance of our preconditioner is independent of the mesh sizes and the number of subdomains.

Conclusion

We have introduced a new additive Schwarz preconditioner to use in parallel finite elements where local meshes are meshes of the whole domain. From a practical point of view, it has the advantage of being able to obtain local matrices through assembling without communication and without forming the global matrix. It is proved to be optimal in the sense that the effective condition number of the preconditioned system can be bounded independently of the

Figure 2 :

 2 Figure 2: Subdomain Ω i (left) and its extension Ω † i (right) on their associated local mesh T i .

Figure 3 :

 3 Figure 3: L-shaped domain: The coarse mesh with partition (left), a local mesh (middle) and the global mesh (right) when L = 0, N = 4 and l = 2

Figure 4 :Figure 5 :Figure 6 :

 456 Figure 4: Geometry of the computational domain

Table 1 :

 1 Smallest and second largest eigenvalues ( λmin , λmax ) of the preconditioned system P -1 A for meshes of different sizes and partitions.

Table 2 :

 2 Numbers of iterations required to reduced the residual by a factor of 10 6 using the proposed preconditioner and two-level AS preconditioner (in parentheses).

			n 0 = 608			n 0 = 1042
	N	l = 1	n = 2	l = 3	l = 4	l = 1	l = 2	l = 3	l = 4
	4	4(10)	4(10)	4(10)	4(10)	4(10)	4(10)	4(10)	4(10)
	8	6(11)	7(11)	7(11)	7(13)	7(11)	7(11)	7(12)	6(15)
	16	8(13)	9(13)	9(13)	8(13)	8(12)	9(11)	9(12)	8(14)
	32	11(13) 12(13) 11(13) 11(17)	11(13) 11(12) 11(12) 11(15)
	64	13(15) 13(

coarse mesh size, fine mesh size and the number of subdomains. In comparison with the traditional two-level AS preconditioner, it does not require extra cost associated with the overlap to maintain the optimal convergence when the mesh is refined. The theoretical findings have been confirmed by numerical experiments.

Acknowledgement

We would like to thank Waad Subber for suggesting the seepage problem and providing the geometry data of the problem. This work was supported by the Numerical Algorithms and Intelligent Software Centre funded by the UK EPSRC grant EP/G036136 and the Scottish Funding Council.