Emma Bell

Shrinking the State? Change and continuity in public service reform

It is often asserted that the transition from New Labour to a Conservative-Liberal Democrat coalition government in 2010 marked a decisive break in terms of public service policy. That break was one characterised in particular by the apparent switch from profligacy to austerity with regard to spending on public services with a concomitant shrinking of the State. This paper seeks to demonstrate that this narrative masks considerable continuity between the two periods, indeed over the past thirty-five years. It begins by demonstrating that the change of direction in economic policy, though significant, was not as unambiguous as it may appear. It then notes that, in any case, this change did not lead to any diminution of state power. On the contrary, as the private sector has come to play an ever-greater role in the delivery of public services, the British State has further extended its already significant role in legitimising and facilitating the marketisation of public services, thus promoting corporate welfare. Meanwhile, the demos have found themselves disempowered, regardless of the discourse of localism and the promised decentralisation of power from the centre.

Résumé

On affirme souvent que la transition des néotravaillistes vers un gouvernement de coalition libéral-démocrate en 2010 a signalé une rupture décisive dans la politique à l'égard des services publics. Cette rupture aurait été notamment marquée du passage du laxisme budgétaire à l'austérité avec une diminution concomitante du pouvoir de l'État. Cet article cherche à démontrer que ce récit dissimule une grande continuité entre les deux périodes, voire depuis ces derniers trente-cinq ans. Sera affirmé en premier lieu que le changement de politique économique, bien qu'il soit important, n'était pas sans ambigüité. De toute façon, ce changement n'a aucunement affaibli l'État. Au contraire, alors que le secteur privé joue un rôle grandissant en tant que fournisseur de services publics, l'État britannique a renforcé son rôle déjà conséquent dans la légitimation et la marchandisation des services, ainsi favorisant l'assistanat étatique des entreprises. Simultanément, le pouvoir des citoyens a été affaibli, en dépit du discours sur le localisme et la décentralisation du pouvoir étatique.

Much has been made of the potential of the Conservative Party's public spending plans over the past six years to reduce the size of the State. David Cameron explicitly committed to 'building a leaner, more efficient state', claiming that 'we need to do more with less. Not just now, but permanently'. [START_REF] Cameron | speech at Lord Mayor's Banquet[END_REF] The former Chancellor George Osborne's announcement to shrink total government spending to little over 35.2 per cent of GDP before the end of the decade was hailed by the Daily Telegraph as 'big news', leading to a shrinking of the State back to pre-welfare state levels. [START_REF] Warner | George Osborne's plan to shrink the state is big news[END_REF] For the Oxford economist Simon Wren-Lewis, Osborne's plans represented 'a shrinking of the UK state that is unprecedented'. [START_REF] Wren-Lewis | Understanding George Osborne[END_REF] The public services, with the exception of ring-fenced services such as education and healthcare, were to bear the brunt of government spending cuts, with unprotected government departments seeing their budgets cut by over 20% on average between 2010 and 2015. [START_REF]Election 2015: Public Spending[END_REF] Yet, far from negatively affecting the quality of these services, the government promised they would unleash a veritable 'revolution' in the public sector by transferring power from the State to ordinary people and improving accountability mechanisms. [START_REF] Government | Open Public Services White Paper, Cm8145[END_REF] It was thus suggested that the arrival of the Conservative-led coalition government to power in 2010 marked a significant break from the past, not just from the profligate New Labour era but also from previous Conservative governments who, whilst attempting to 'roll back the State', had never attempted anything quite so ambitious with regard to public service reform. This paper aims to challenge these claims of novelty and demonstrate the essential continuity in this field over the past thirty-five years and more, despite clear differences of style and emphasis. It begins by challenging claims that New Labour and recent Conservative-led governments have been characterised by the dichotomy between profligacy and austerity. It focuses on the extremely important role played by the British State in manipulating the public discourse to create hegemonic consensus about the most recent crisis of capitalism and the need for austerity. It is then demonstrated that there has been no revolution in terms of citizen empowerment that might mark a clear break from the New Labour era -on the contrary, the march towards post-democracy has continued apace [START_REF] Crouch | The March Towards Post-Democracy, Ten years on[END_REF] as the 'public' nature of public services has been eroded. Although this change has been underpinned by the huge increase in power of the private sector, there has been no shrinking of the state in favour of the latter either. Indeed, it is argued that the very concept of a shrinking state is a misleading and simplistic one which tends to automatically equate spending power and political power. In reality, the State continues to fulfil key political functions, not least with regard to public spending. Importantly, it continues to play a significant role in supporting the private sector via the creation and regulation of new markets, the distribution of various forms of corporate welfare and the adoption of mechanisms to neutralise obstacles to market 'freedom'.

From profligacy to austerity?

It is commonly thought that the New Labour years were characterised by profligacy in public spending which contrasts sharply with the austerity of Conservative-led governments since 2010. Conservative leaders certainly sought to reaffirm such perceptions in an attempt to cast themselves as the Party to be trusted with the public finances and to frame the crisis as being fiscal rather than financial in nature. As David Cameron affirmed in 2010, 'there isn't really any government money left' since 'Gordon spent it all'. [START_REF] Cameron | Speech: Big Society vs Big Government[END_REF] It is certainly true that total public spending was very high in 2010, standing at 53.4 per cent of GDP, compared to 40.6 per cent in 1997. [START_REF] Chote | Public Spending Under Labour: 2010 Election Briefing[END_REF] Before the financial crisis hit, it was considerably lower -44.1 per cent of GDP in 2007 -but it nonetheless increased in the period 2000-2006 by 4.8 per cent a year, with spending on public services reaching 6.4 per cent a year during the same period. 9 Overall, spending on public services between 1997 and 2010 averaged 4.4% per year, compared with just 0.7 per cent a year under the previous conservative governments from 1979-1997. 10 It was nonetheless a gross exaggeration to suggest that New Labour was entirely lax with the public finances. Firstly, increases in public spending largely focussed on key areas such as the NHS, education and transport. New Labour spending on some areas, notably social security and to a lesser extent defence, was actually lower than under previous conservative governments. 11 Furthermore, public sector net debt as a percentage of GDP was lower in 2008 (37 per cent) than in 1997 (42 per cent). [START_REF] Wren-Lewis | Mediamacro Myth Two: Labour profligacy[END_REF] It is hardly surprising that it rose once the economy went into recession. In any case, Britain's debt in 2010 was not unprecedented -indeed, it was low by historic standards and lower than what Labour had inherited in 1997 (when presented as a percentage of GDP rather than in absolute cash terms). [START_REF] Gamble | Austerity as Statecraft[END_REF] What was unprecedented was not the debt but rather the size of the bank bailout, amounting to £512 billion for the British taxpayer. [START_REF]Maintaining the Financial Stability of UK Banks: Update on the support schemes, report by the Comptroller and Auditor General[END_REF] Whilst this had a major impact on public sector debt, the debt was not unmanageable. As a number of experts have pointed out, the British government, unlike countries such as Greece, could still borrow at very favourable rates in the international financial markets in its own currency and could, in any event, always print more money. [START_REF] Gamble | The Austerity Delusion[END_REF] Nonetheless, austerity was presented as the only way forward by the Conservative-led coalition government, an assertion that went largely unchallenged by Labour, at least until 2015 following the election of Jeremy Corbyn to the leadership. The austerity agenda was rapidly announced by the former Chancellor George Osborne in the Emergency Budget that was called just a matter of weeks after the general election of 2010. Osborne pledged to cut public sector borrowing from 10.1 per cent of GDP in 2010 to just 1.1 per cent in 2015, principally via public spending cuts. [START_REF] Osborne | Speech to the House of Commons introducing the Emergency Budget[END_REF] In the event, these cuts turned out to be lower than planned and hard-line austerity short-lived as the deficit-reduction plan was watered down after Osborne's first two years as Chancellor. Spending on public services such as health continued, and indeed continue, to increase even though NHS spending is set to fall significantly as a percentage of GDP. [START_REF] Appleby | NHS Spending: Squeezed as never before[END_REF] Whatever the rhetoric, the State will continue to play a significant role in supporting public services and in wealth redistribution. Indeed, spending on welfare increased in both absolute terms and as a percentage of all government spendingup from 33 per cent in 2010/11 to 35 per cent in 2014/15. [START_REF]How is the Welfare Budget Spent?[END_REF] As Le Grand has pointed out, there is much continuity here, not just with New Labour governments, but with the Thatcher governments. [START_REF] Grand | Continuity and Change: Public service reform from Thatcher to the Coalition[END_REF] Then, as now, the State has had to assume the costs of recession and unemployment which will remain high, no matter how great attempts to reduce the welfare budget.

Yet, even though austerity was not as radical as advertised, this did not mean that it did not have serious consequences. The average cuts for unprotected departments, such as work and pensions, were severethey have been estimated at over 20 per cent for the period 2010-11 to 2015-16. [START_REF]Election 2015: Public Spending[END_REF] Austerity was in practice highly selective. A number of reports have shown that it is the poorest that have borne the brunt of austerity measures such as the limitation of social care, child care, youth services, housing services, and legal advice. [START_REF] Slay | Penny Surviving Austerity: Local voices and local action in England's poorest neighbourhoods[END_REF] These are the public services that have been most impacted, especially as a result of cuts to local government budgets. Indeed, spending by local authorities in England on services other than education, health, police and fire services was cut by 23.4 per cent per person in real terms between 2009 and 2015. [START_REF] Innes | Central Cuts, Local Decision-Making: Changes in local government spending and revenues on England, 2009-10 -o 2014-15[END_REF] Further cuts are likely following the former Chancellor's announcement in the last budget (2016) of another £3.5bn reduction in public spending by 2020.

Meanwhile, it might be suggested that a certain degree of profligacy has been practiced at the top of the economic ladder as tax breaks have been awarded to top earners and corporations. The decision to slash corporation tax to just 20 per cent (and subsequently to 17% by 2020) was described by Jenkins as a 'reckless' measure from a purportedly 'austere' chancellor. [START_REF] Jenkins | How Janus-faced George Osborne defied stereotype and triumphed[END_REF] The focus on public spending rather than taxation as a means of reducing the deficit suggests that this was not a neutral policy of simple fiscal consolidation. Indeed, for many economists, austerity was not even necessary and may in fact have delayed economic recovery in the UK. 24 They suggest that Conservative-led austerity policies were not adopted out of economic necessity but rather out of political expediency.

Austerity as hegemony

Gamble has explained austerity in terms of 'statecraft'. For him, it can be understood as a political strategy to pin the blame for the financial crisis on 'irresponsible' Labour economic policy and thus prove its own economic competence. 25 Wren-Lewis has developed what he terms a 'general theory of austerity' whereby the former Chancellor flew in the face of economic evidence about the dangers of austerity in order to reduce public spending. 26 Although the concept of 'a general theory of austerity' suggests a coherent plan, Wren-Lewis regards it as more opportunistic than a carefully thought-out strategy. This assertion would seem to be supported by the fact that the Conservative Party actually supported Labour spending plans up until the crisis hit in 2007. [START_REF] Lee | We Are All in This Together" : The Coalition agenda for modernisation[END_REF] Nonetheless, austerity came to be accepted as the only way forward, even for a time by the Opposition. How was this done? Wren-Lewis highlights the British government's misleading reframing of the crisis as one of public spending in order to justify the focus on the need for reductions in the latter over any focus on taxation as a possible solutionhe terms this strategy the 'deficit deceit'. The simple (and erroneous) analogy between government and household budget was regularly invoked to convince the general public of the need to 'live within their means'.

Whilst reducing public spending is often regarded as strategy to 'shrink the state' (as asserted by Wren-Lewis amongst others), the role of the State was actually reinforced in the course of this reframing of the public debate over economic policy. Indeed, the State played a vital role in creating hegemonic consent around the austerity project. Clarke and Newman have explained with alacrity how this was done. Firstly, the crisis was 'nationalised' as blame was apportioned to New Labour rather than to the failures of global financial capitalism. [START_REF] Clarke | What Crisis is This?[END_REF] This justified swift and drastic action by the nation state to remedy the crisis. Secondly, the crisis was also personalised, presented as one caused by irresponsibility of individual citizens to live within their means and be self-sufficient [START_REF] Clarke | The Alchemy of Austerity[END_REF] . Thirdly, the crisis was transformed into a crisis of morality, caused by the immoral behaviour of citizens who had failed to 'pull their weight', thus causing the state to use the hard-earned taxes of those in employment to subsidise the lazy. This was the 'alchemy of austerity', the means via which consent was sought and won (at least temporarily) for a policy that ought to be inherently unpopular.

Power to the People: A devolution revolution?

An important part of the discourse securing consent for austerity was the idea that reduced public spending might provide an opportunity for ordinary citizens to seize power from the State. Again, this policy was presented as a point of rupture from the overbearing, authoritarian State that many believed had come to characterise the New Labour years. In 2015, the Treasury promised a 'devolution revolution' whereby more power would be devolved not just from central government to Scotland, Wales and Northern Ireland but also to local government in England. [START_REF] Treasury | Spending Review and Autumn Statement[END_REF] Most central government funding is to be replaced by funding from local business rates which may be used to finance local services. It is claimed this will provide local government with 'new levers of power to generate growth for their area'. 31 That power will entail being able to fix local business rates without government intervention but this gives councils little real power over the future of local services if such rate-fixing fails to bring in extra revenue. The risk is that this will leave some local councils impoverished whilst councils in areas with thriving businesses will end up wealthier, despite promises of alternative sources of funding for the former. [START_REF] Harris | Austerity and then chicanery: how the Tories target cash-strapped Labour councils[END_REF] It practice, it would seem that cash-strapped local government is being given responsibility to drive down costs without real power to shape local policy.

The policy might be regarded as a continuation of the localism agenda implemented under the coalition government whereby 'power and control [would be pushed] away from the centre and into communities and neighbourhoods'. [START_REF] Maude | Evidence provided to the House of Commons Public Administration Select Committee[END_REF] The Localism Act of 2011 had already given councils a 'general power of competence', enabling them to do anything an individual can legally do, such as establishing new services and partnerships without having to first seek the approval of central government. Yet, as the Department for Communities and Local Government made it clear, the aim was primarily 'to provide them more freedom to work together with others in new ways to drive down cost'. [START_REF]Department for Communities and Local Government, A Plain English guide to the Localism Act[END_REF] With regard to public services, the localism agenda entailed making them more 'open', introducing further deregulation in order to 'free [their] staff from the bureaucracy and central instruction that previous governments have used to run public services' and to 'free' service users by giving them 'a choice about the services they use'. [START_REF] Hm Government | Open Public Services White Paper[END_REF] Far from being new, this policy was actually very much in line with previous policies: with the Thatcherite agenda of improving 'consumer' choice and control over public services; and with Blair's drive to empower individuals by encouraging them to recognise their responsibilities to become more involved in shaping those services.

In each phase of reform, the State has remained highly interventionist in directing localism from above. The Thatcher governments were notoriously dirigiste, especially with regard to local government, imposing enterprise zones and the poll tax against the will of local councils, implementing swingeing spending cuts and abolishing the Greater London Council (GLC) and the six metropolitan county councils. The Blair governments came to power criticising top-down control of local government and promising to give them more flexibility to respond to local needs and provide the services that citizens and communities want. The Cameron-led government promised to take this agenda of citizen empowerment further in a move that seemed to represent a real rupture from previous Conservative governments. Yet, despite these apparently different approaches, the underlying logic was the same: as New Labour put it, to ensure that 'councils will have to challenge traditional methods of delivery' and 'root out waste'. [START_REF] Hm Government | Strong and Prosperous Communities: The Local government white paper[END_REF] In practice, this meant working in closer collaboration with the private sector.

Whilst ordinary people were encouraged to get involved in local service delivery, most strikingly under the Conservative Party's so-called 'Big Society' project, in practice, it was the private sector that was to dominate the new mode of service delivery. In the field of education, for example, the government's 'academisation' programme, initially launched under the last Thatcher government, pursued under New Labour and extended on an unprecedented scale by Conservative-led governments since 2010, [START_REF] Griffiths | Education Policy: Consumerism and Competition[END_REF] has privileged private sector involvement in education, despite government discourse concerning parental control. [START_REF] West | The Development of the Academies Programme: "Privatising" school-based education in England 1986-2013[END_REF] Although academies and their latest variant, free schools, continue to receive government funding, they are actively encouraged to seek private sector sponsors and to outsource ancillary services, infrastructure modernisation projects, and even school management, to private companies. Meanwhile, the role of parents may be reduced -a government white paper dating from March 2016 even suggested removing parents from school governing boards in favour of professionals with experience in business and finance.

Another instructive example of the increasing role of the private sector in public service delivery is that of the probation service. Following the dissolution of the State-run Probation Service in June 2014, the private and voluntary sectors were encouraged to become involved in service provision. Yet, despite the fact that voluntary sector services, based as they are in the local community, are well-placed to provide specialist services, they are increasingly crowded out of the market. In practice, community services find it extremely difficult to compete for bids on a level playing field with the private sector. In the case of probation services, the large majority of themworth £820 million per yearhave been privatised. [START_REF] Teague | Rehabilitation, punishment and profit: The dismantling of public-sector probation[END_REF] It is consequently hard to assert that public service reform has really empowered local communities. Local initiatives continue to be directed by a strong central state and are often stifled by a powerful private sector. Indeed, the increased role of the latter is eroding the 'public' nature of public services, in particular by the lack of transparency that characterises many government contracts. [START_REF]Contracting Out Public Services to the Private Sector[END_REF] Whilst the transparency of the public sector is not always evident either, at least public bodies remain directly accountable to the demos. The private sector is accountable only to government and, as an increasingly influential governmental partner, it is questionable to what extent accountability is respected in practice. Increased power for the private sector does seem to have led to a loss of power for the public, but the same cannot be said of the State.

Big market, small state?

The rise of corporate power is not a zero-sum game for the State: just because the private sector has more power, that does not mean that the State has less. On the contrary, both the State and the private sector have extended their power conterminously. The growth of the public services industry provides a highly illustrative example. Here, the private sector has come to form something of a 'shadow state' whereby a small number of companies have come to play an extraordinarily important role in the delivery of public services. [START_REF]The Shadow State: A report about outsourcing of public services[END_REF] Indeed, the value of outsourced public services has increased significantly in recent years to reach more than twice its value in 2000estimated at well over £80bn. [START_REF]The State of the State 2014-15: Implications for private sector outsources[END_REF] This acceleration has only been assisted by the context of austerity, regarded as an opportunity by the private sector.

The State has played an extremely important role in the creation of new markets in the public sector for private business. From privatisation to PFI (the private finance initiative), the government has helped to sell the merits of private-sector involvement in public service delivery, presenting it as a way of improving service quality and promoting consumer choice.

The discourse of austerity provided further justification, as finding alternative sources of funding for services was presented as a necessity in the context of massive public spending cuts. The government thus created new 'opportunities' for the private sector. These opportunities are likely to be further extended, not just to British companies, but also to international corporations. Although Britain's exit from the EU may leave her exempt from the TTIP (Transatlantic Trade and Investment Partnership) which threatens to open up all public services to commercialisation, 43 the CETA (Comprehensive Economic and Trade Agreement) signed between the EU and Canada before Britain leaves the EU will ensure the UK will have to comply with its terms regardless, at least for another twenty years. This will mean that public services in Europe will be open to marketisation to Canadian companies and companies from other nations that happen to operate there. It is also likely that a UK outside the EU will seek to negotiate its own trade deal with the United States, thus further opening up the market in public services.

The State therefore plays a significant role in the creation of new markets in the public sector. But it also continues to act as overseer of those markets. People continue to look to government as the ultimate guarantor that good quality public services are delivered. In practice, therefore, government continues to play a big part in managing the market. As the National Audit Office noted, 'the introduction of market mechanisms into public service delivery does not remove the role of government' -it is up to government to 'make the market work effectively'. [START_REF]Delivering Public Services Through Markets: Principles for achieving value for money[END_REF] It thus seeks, for example, to impose regulatory control to ensure that services reach certain standards as well as promoting value for money. Hence, the establishment of bodies such as Monitor, now NHS Improvement, charged with overseeing public and private NHS services. Similarly, the last government sought to incentivise public providers to provide quality services by introducing payment-by-results. In practice, such regulation has not prevented serious malfunction such as when G4S was found to have overcharged the Ministry of Justice for the electronic tagging of offenders, some of whom were dead. Although the company was heavily fined, it continues to provide public services from NHS transport services to residential children's homes.

Far from ensuring that the market functions efficiently, government intervention distorts the market, allowing it to be dominated by what are effectively, in the words of the House of Commons Public Accounts Committee 'privately-owned public monopolies' funded by the tax-payer. [START_REF][END_REF] As Crouch and others have pointed out, markets in public services have become oligopolistic, dominated by a very small group of actors (notably G4S, Serco and Capita) that survive in a symbiotic relationship with rather than as an alternative to the State. [START_REF] Crouch | The Paradoxes of Privatisation and Public Services Outsourcing[END_REF] They are dependent on public money whilst the government has come to depend on them on the same way as it came to depend on the large banks that were deemed 'too big to fail'. 47 This symbiotic relationship goes a long way to explaining the extent to which the State supports the private sector through corporate welfare, described by Farnsworth as 'public policies that directly or indirectly meet the specific needs and/or preferences of private businesses'. [START_REF] Farnsworth | Public Policies for Private Corporations: The British corporate welfare state[END_REF] He regards the policy of contracting out public services to the private sector as just one of many forms of corporate welfare since it enables companies to make extra profits that they could not have made had they been competing in a normal competitive market. [START_REF] Farnsworth | The British Corporate Welfare State: Public provision for private businesses[END_REF] He estimates the cost of these profits to the UK government at £15bn per year (out of a total sum of £238bn government expenditure of procurement overall). 50 Added to this are the costs of government subsidising low wages in the contracted out public sector, not to mention the cost of corporate tax cuts.

Finally, the State also supports the private sector in removing barriers to the 'free market'. As under the Thatcher governments, its authoritarian arm continues to be deployed against those who oppose market reforms. Although the police themselves protested against public sector cuts, they were deployed to use much-criticised 'kettling' tactics (restricting the free movement of protesters via the use of steel cordons) against striking public sector workers, notably in November 2011. Furthermore, the law itself was strengthened against trade union activity. Building on existing legislation introduced under the Thatcher era, the Trade Union Act 2016 stipulates that for industrial action to be lawful, it has to have the support not just of the majority of workers voting in a ballot but at least 50% support of all those eligible to vote (40% in certain 'important public services' including health and education). In any case, and again in parallel with the 1980s, public sector unions had most probably been weakened by huge cuts in public sector jobs which have left the number of people working in the public sector at its lowest level in 40 years. [START_REF] Cribb | The Public Sector Workforce: Past, present and future[END_REF] Job insecurity, pay and pension cuts likely weakened public sector unions' ability to use industrial action as a weapon. [START_REF] Scott | The Coalition Government and Employment Relations in the Public Services[END_REF] Indeed, while the tough line taken by recent governments against the trade unions might suggest otherwise, levels of strike action have actually been very low in recent years by historical standards. Weakening the trade union movement may have been a desired outcome of cutting public sector jobs. [START_REF] Reed | Osbornomics[END_REF] The path was thus smoothed for the entry of private sector competitors into the public sector.

Conclusion

Despite some clear differences in approach to public services over the past thirty-five years, the period has been marked by more continuity than change. The dichotomy between conservative austerity and labour profligacy has not been so great as advertised. Whilst spending on public services under Blair was certainly higher than under the previous government, it was by no means excessive and was targetted on the very same services that were ring-fenced from the worst cuts by subsequent Conservative governments. Similarly, austerity, whilst evident in some areas such as local government, was not as great as advertised: spending increased on health and education even if it fell as a percentage of GDP, whilst the welfare bill, as under the Thatcher governments continued to rise in spite of cuts.

More important than austerity itself was the discourse of austerity. Paradoxically, whilst austerity was promoted as a means of shrinking the State, the very fact that the State played a key role in articulating this same discourse actually ensured that the State played a highly interventionist role in creating hegemonic consensus around the Conservative neoliberal project. Indeed, the most important point of continuity in recent decades has been the significant role played by the British State. Far from shrinking, it has transformed itself, despite the discourse of localism and the apparent devolution of power from the centre.

Whilst it may take less responsibility for ensuring the welfare of its citizens, it now plays an even greater role in promoting the welfare of the private sector, opening up new markets for it to exploit, allowing publicly-sponsored monopolies to develop, subsidising company profits and neutralising opposition by framing public discourse and taming the unions. As a result, the State and the private sector have developed a symbiotic relationship based on mutual dependence. The context of the financial crisis and the discourse of austerity merely provided a new opportunity for the acceleration of pre-existing trends.

Despite headline-grabbing announcements of a change of direction under Theresa May, it seems unlikely that a change of leadership will lead to significant policy change.

There will be no end to austerity. Whilst the new chancellor may have promised to restore fiscal discipline 'in a pragmatic way', local government is locked into agreements to reduce their budgets until at least 2020 and there has been no promise to increase spending to make up for the shortfall in the health and education budgets. [START_REF] Hammond | speech to the Conservative Party Conference[END_REF] In any case, the discourse of austerity, or at least of fiscal consolidation, will remain important, justifying the continued contracting out of public services to the private sector. Meanwhile, the new context of a looming Brexit will justify a continued expansion of the State in its support of the private sector, with Hammond pledging to provide whatever support is necessary to protect British businesses as they make the transition to living outside the EU.

Notes


Alice Raeli

Michel Bergmann

Angelo Iollo

A Finite-Difference Method for the Variable Coefficient Poisson Equation on Hierarchical Cartesian Meshes

Keywords: Finite difference method, Hierarchical Cartesian grid, Octree/Quadtree, Variable coefficient Poisson equation

We consider problems governed by a linear elliptic equation with varying coefficients across internal interfaces. The solution and its normal derivative can undergo significant variations through these internal boundaries. We present a compact finite-difference scheme on a tree-based adaptive grid that can be efficiently solved using a natively parallel data structure. The main idea is to optimize the truncation error of the discretization scheme as a function of the local grid configuration to achieve second-order accuracy. Numerical illustrations are presented in two and three-dimensional configurations.

Introduction

Many applications like for example incompressible multi-phase fluid flows or heat conduction in non-homogeneous materials are characterized by strongly varying physical parameters across internal interfaces. In classical approaches these interfaces are treated like internal boundaries using interface fitted meshes, see for example [START_REF] Jelassi | A substructuring method for phase change modelling in hybrid media[END_REF] for a recent heat-conduction application. These methods are accurate and can lead to simple discretization schemes of the interface conditions. However, grid generation and handling can be costly and cumbersome when the interface geometry is evolving in time. Furthermore, solution in parallel typically requires time-dependent partitioning of the grid that induces additional computational costs.

In the present approach we use non-conforming hierarchical meshes to discretize the solution. The hierarchical nature of the grid makes mesh generation, adaptivity and partitioning very efficient and with a low-memory footprint. Since the grid is non conforming to these internal boundaries, discontinuous coefficients are regularized across the interfaces. Accuracy is then recovered thanks to grid adaptivity. [START_REF] Johansen | A cartesian grid embedded boundary method for poisson's equation on irregular domains[END_REF] were among the first to propose adaptive block-cartesian meshes to solve the Poisson equation. They proposed a cellcentered second-order scheme based on local quadratic reconstructions. In the same spirit Howell and Bell [1997] solved a Poisson problem within a projection method for incompressible viscous flows using a quadratic reconstruction ghost-cell approach to recover appropriate accuracy at the border between different blocks. A different setting was proposed by [START_REF] Popinet | Gerris: a tree-based adaptive solver for the incompressible euler equations in complex geometries[END_REF] to solve the incompressible Euler equations with octree grids. For the Poisson solver, the author proposes a cell-centered discretization scheme using all first neighbours in order to recover a second-order approximation as a function of the local grid configuration. [START_REF] Losasso | Simulating water and smoke with an octree data structure[END_REF] proposed a Poisson solver on octree which converges to the actual solution with second-order accuracy. This approach allows a discretization matrix which is symmetric so that the convergence rate of the iterative solvers is significantly improved. [START_REF] Min | A supra-convergent finite difference scheme for the variable coefficient poisson equation on non-graded grids[END_REF] recover a higher-order accuracy with a compact stencil at the price of moving from a cell-centered scheme to a vertex-centered scheme. Other examples of node-centered schemes with a direct application to level set methods are given in [START_REF] Losasso | Spatially adaptive techniques for level set methods and incompressible flow[END_REF]- [START_REF] Mirzadeh | Parallel level-set methods on adaptive tree-based grids[END_REF].Parallel optimized performing algorithm that handle node-centered operations are given in [START_REF] Burstedde | p4est: Scalable algorithms for parallel adaptive mesh refinement on forests of octrees[END_REF], whereas a finite element application is performed [START_REF] Bangerth | Algorithms and data structures for massively parallel generic adaptive finite element codes[END_REF]. Finally, a Poisson solver based on a finite-volume approach with a least-square reconstruction of the fluxes at the octree level jumps is proposed by [START_REF] Olshanskii | An octreebased solver for the incompressible navier-stokes equations with enhanced stability and low dissipation[END_REF]. More recently, a Voronoi Interface Method is presented by [START_REF] Guittet | Solving elliptic problems with discontinuities on irregular domains-the voronoi interface method[END_REF] for general elliptic problems with subdomain discontinuities. In this approach additional degrees of freedom are placed close to the subdomain interface and a Voronoi partition centred at each of these points is used to discretize the equations in a finite volume approach. The solution obtained is secondorder accurate.

In this work we present a cell-centered finite-difference scheme to solve a variable coefficient Poisson equation on quadtrees and octrees. The main idea of the method is to optimize the truncation error of the elliptic operator discretization as a function of the local grid configuration. The optimization problem solution is local, fast and it involves only the first neighbours in order to reduce communications in parallel. The scheme is second-order accurate when the coefficients vary smoothly through the domain. In the following we describe the method and assess its consistency, accuracy and extension to general hierarchical grids in two and three dimensions. Numerical illustrations are presented in two and three-dimensional configurations.

Problem Definition

We consider a configuration representing an idealized composite medium. A domain Ω is subdivided in two parts, G and S. We suppose that different diffusion parameters characterize the two sub-domains (Fig. 1); we have Ω = G ∪ S and γ the interface between both sub-domains. We distinguish Neumann Γ N and Dirichlet Γ D boundary conditions on the external boundary. The variable coefficient Poisson problem we consider is modeled by:

-div(κ(x)∇u(x)) =g(x) in G ∪ S, (1a)
∂ n u(x) =0 on Γ N , (1b) u(x) =u D (x) on Γ D , (1c)
[κ(x)∂ n u(x)] =0, [u] = 0 on γ, (1d)
where x ∈ R n are the spatial coordinates and κ(x) is piecewise continuous on each subdomain but possibly discontinuous across γ. In that case, the solution u(x) is continuous all over the domain G ∪ S and the normal derivatives are discontinuous across γ.

In the following we will initially describe the data structure. Then we consider the Laplace operator and investigate its discretization, consistency and accuracy. We moreover detail how to accurately impose Dirichlet boundary conditions on unfitted grid boundaries via penalization and hierarchical grid refinement. The variable coefficient Poisson equation in the limit of discontinuous parameters is finally considered.

Hierarchical grid data structure

We consider a hierarchical data structure based on the principle of recursive decomposition of space. The decomposition is done into equal parts on each level. Each internal node has exactly four children (quadtree) for two-dimensional problems, and eight children (octree) for three-dimensional problems. The quadtree is defined in a square, the octree in a cube. For simplicity reasons, we describe the data structure in two dimensions (Fig. 2). The data structure is based on a linear octree Frisken and Perry [2002], therefore only the leafs of the tree structure (see Fig. 2) are stored. This linear data structure is easily dispatched to a distributed memory architecture. In order to limit parallel communications, we constrain the discretization scheme to include only the first layer of neighbouring cells. We use a cell centered scheme because it is easier to handle, but the overall process can be applied to vertex center schemes. In what follows we will refer to each point in the space as a cell or octant. Each cell may be the parent of four (eight in 3D) children. The root cell is the base of the tree (often it represents the entire region before the discretization) and a leaf is a cell without any child. The level of a cell is defined by starting from zero for the root cell and by adding one every time a group of descendant children is appended. Each cell C has two kinds of neighbours: through faces following the axial directions and through corners following its diagonals directions. Hierarchical grids are defined graded (or balanced) if the levels of all neighbouring cells do not differ by more than one. This constraint has little impact on the flexibility of the discretization we propose but it may allow a gradual refinement by increments of two. In the following, we will mainly focus on graded grids but we will present typical results on non-graded grids in order to stress that the scheme can be applied without modifications.

The octree data structure is designed based on the following requirements: i) efficient access to neighbouring cells; ii) efficient access to cell positions and their levels; ii) efficient access to stored data. To this end, we assign a Z-order index to each cell [START_REF] Guy M Morton | A computer oriented geodetic data base and a new technique in file sequencing[END_REF], Fig. 3) thanks to the library PABLO1 .

We classify the neighbours topology of an octant using a base-5 8-digits numerical key (resp. 26-digits for the 3D case). We define a function of the level: [L] := L -nL, with L the level of the actual octant and nL the level of the neighbour. The values attributed to the key elements are presented in Table 1. An example of this construction is given in Figure 4 .

Assigned value

Possible cases 0 neighbour on this side 1

[L] = 0 2 [L] = 1 3 [L] = -1 4 [L] = 2 5 [L] = -2
Table 1: Key values attribution. This key has the following properties: it is bijective, it is easy to build and to interpret, and it is independent of the cell dimensions, i.e., the tree level. The use of this key can lead to a significant speed up in the grid pre-processing phase.

4 Cell-centered finite-difference discretization of the Laplacian

In this section we present the main idea to discretize the Laplacian. A similar approach is used for the gradients.

There are two natural choices to discretize differential operators on hierarchical grids: vertex-centered [START_REF] Min | A supra-convergent finite difference scheme for the variable coefficient poisson equation on non-graded grids[END_REF] or cell-centered [START_REF] Popinet | Gerris: a tree-based adaptive solver for the incompressible euler equations in complex geometries[END_REF]. Here we considerer a cell-centered scheme. In this case, thanks to the data structure we use, the neighbour configuration is more easily accessible compared to a vertex-centered scheme.

The main idea is to ensure consistency and second-order accuracy of the truncation error in the sense of finite differences as a function of the number of neighbours. Let us focus on a two-dimensional problem and let us consider the configuration in Fig. 5. As shown by [START_REF] Min | A supra-convergent finite difference scheme for the variable coefficient poisson equation on non-graded grids[END_REF], if only face-adjacent cells are to be used to discretize the Laplace operator in c 4 , then there is no locally consistent linear scheme in the sense of finite differences. Instead, we discretize the Laplace operator in c 4 using all the points belonging the first layer of neighbours. This will allow us to obtain more degrees of freedom than sufficient constraints for consistency. Possibly, as a function of the number of available points and symmetries, we will also ensure sufficient conditions for second-order accuracy. To see this, let h be the side length of the cell c 4 . To obtain a consistent scheme we must ensure that the discretization coefficients a i , 1 ≤ i ≤ 7 satisfy: a 2 u 2 + a 3 u 3 + a 4 u 4 + a 5 u 5 + a 6 u 6 + a 7 u 7 + O(h). Using standard Taylor analysis, we expand for example the solution u 3 in c 3 with respect to u 4 in c 4 and get:

u xx + u yy = a 1 u 1 +
u 3 = u 4 -h ∂u 4 ∂x + h 2 2 ∂ 2 u 4 ∂x 2 + O(h 3 ).
Similarly, all the other points are expanded with respect to c 4 . A complete Taylor analysis on all the involved neighbours leads to the following linear system:

         1 1 1 1 1 1 1 0 -h 0 -h 3h 2 -h 2 3h 2 0 h h 0 h 2 -3h 2 -3h 2 0 h 2 2 0 h 2 2 9h 2 8 h 2 8 9h 2 8 0 -h 2 0 0 3h 2 4 3h 2 4 -9h 2 4 0 h 2 2 h 2 2 0 h 2 8 9h 2 8 9h 2 8                    a 4 a 1 a 2 a 3 a 5 a 6 a 7           =         0 0 0 1 0 1         .
In the example above we must determine seven discretization coefficients a i , 1 ≤ i ≤ 7 but we only have six constraints for consistency. The idea is to ensure consistency and, at the same time, to minimize the deviation from second-order accuracy as follows.

In the general case, when the number of contraints is m, we solve the constrained minimization problem by defining an appropriate Lagrangian function. Let λ ∈ R m a vector of Lagrange multipliers, a ∈ R n the discretization coefficient vector of size n (the size of the stencil), M ∈ M m,n (R) the constraint matrix, f ∈ R m the right hand side vector corresponding to the imposed constraints and F (a) a convex cost function from R n to R. We define a Lagrangian function L(a, λ) :

R n × R m → R as follows L(a, λ) = F (a) -λ T (M a -f ), (2)
and compute the stationary point of this function with respect to (a, λ):

∂L(a,λ) ∂a = 0, ∂L(a,λ) ∂λ = 0. ⇔ ∂F ∂a -M T λ = 0, M a = f.
Let B ∈ M 6,n the sub-matrix corresponding to the consistency constraints, C ∈ M 4,n the sub-matrix relative to the second-order constraints, α ∈ [0, 1] and let h = 1. The discretization coefficients are then rescaled dividing by the appropriate value of the cell side. We distinguish two cases:

• n ≤ 10 : M = B and we take F (a) = 1/2a T (1 -α)C T C + αI a and the local system to be solved is

((1 -α)C T C + αI) -B T B 0 a λ = 0 f .
This choice of the convex function F (a) is such that the discretization coefficients minimize the second-order truncation error encoded in matrix C and their norm is penalized by coefficient α. We have chosen a small value of α that results in a stable matrix to invert and that introduces the minimal amount of regularisation. We took α = 0.01 for all the numerical illustrations in the following. The coefficients a always satisfy 6 consistency constraints.

• n > 10 :

M = B C F (a) = 1/2a T a m = 10 I ∈ M n,n I -M T M 0 a λ = 0 f .
The coefficients satisfy 10 second-order accuracy constraints while their norm is minimized.

This approach is independent of the specific grid configuration and can be applied to either graded or non-graded grids. Although we use a cellcentered stencil, this method can in principle be applied to vertex-centered stencils. We remark that the minimal number of available points including only the first neighbours in 2D is 7 if the grid is graded and 6 if the grid is non-graded. Therefore, the discretization will always be at least consistent.

Remark 4.1 (Uniform mesh) The discretization weights (Fig. 6) are -1. 3 for the red point (center of the configuration), -0. 3 for the face adjacent cells marked in green and 0. 6 for the corner blue points. The resulting truncation error weights ensures order two convergence.

Remark 4.2 (Three-dimensional extension) The neighbours are found through faces, edges and vertexes. The consistency constraints are 10, the number of equations to obtain second order accuracy is 20. For either graded or non graded grids, the scheme will be at least consistent since with graded grids we have at least 15 available points including only first neighbours and with non-graded 11. Beyond 30 available points, in order to limit the size of the stencil, we consider the minimum number of all possible neighbours satisfying consistency and second-order accuracy. Hence, where possible, neighbours through edges are not considered and the stencil takes into account only neighbours through faces and vertices. 5 Internal boundaries

Dirichlet boundary conditions and penalization

Internal boundaries with Dirichlet type conditions are modeled by a penalty term [START_REF] Angot | A penalization method to take into account obstacles in incompressible viscous flows[END_REF]. Let χ c be the characteristic function of a given domain c, e.g., the circle in Fig. 10. Let us consider the equation

∆u ε = g - χ c ε (u ε -u 0 ). ( 3
)
We set u ε = u + εũ to derive the equations satisfied by u and ũ. By identifying the terms of the same order in ε we have χ c (u -u 0 ) = 0 and ∆u = χ c ũ. This formally implies that u = u 0 in the circle and ∆u = g outside. Further analysis [START_REF] Carbou | Boundary layer for a penalization method for viscous incompressible flow[END_REF] shows that u ε -u 2 = O( √ ε). The numerical discretization of the penalized model on an unfitted boundary will introduce an additional discretization error of order h, so that the scheme will be only first order accurate. Second-order penalization can be obtained by extrapolation as shown in [START_REF] Chantalat | Level-set, penalization and cartesian meshes: A paradigm for inverse problems and optimal design[END_REF].

Diffusion coefficient discontinuity

In many applications the diffusion coefficient κ(x) can abruptly vary across an interface between two positive constants α and β. However, the normal fluxes are continuous at the interface. We model these problems by the regularized diffusion function

κ(x) = α + (β -α) tanh (σ • Φ(x)) + 1 2 , ( 4
)
where Φ(x) is the signed distance function with respect to the interface of discontinuity and σ the regularization parameter. The signed distance function is obtained by solving |∇Φ(x)| = 1 with Φ(x) = 0 on the interface. Due to regularization, we expect a first-order convergence near the interface (in the infinite norm).

Results and discussion

In what follows, the linear systems are solved using the PETSc library 2 . In most of the following cases, we used a block Jacobi preconditioning (BJA-COBI) on a global flexible GMRES. In two dimensions preconditioning was not strictly necessary. In three dimensions, besides the Jacobi preconditioning, sub-preconditioners of type ILU were employed.

Consistency

We consider here the case κ(x) = 1. The domain is a [0, 1] × [0, 1] square and the grid studied is a bi-periodic lattice obtained by initially repeating the elementary configuration of figure 5 as presented in figure 7. It has been show [START_REF] Min | A supra-convergent finite difference scheme for the variable coefficient poisson equation on non-graded grids[END_REF] that the numerical scheme is inconsistent for this kind of grids if we only use the face neighbours. We thus use all the neighbours including the edge neighbours. The problem to be solved is ∆u(x) = f (x). We considered a test case with the exact solution u e (x 1 , x 2 ) = sin (x 1 -0.5) 2 + (x 2 -0.5) 2 . The convergence table 6.1 is obtained by subsequently subdividing each cell. A second-order accuracy is obtained for both L 2 and L ∞ norms. An example of the error distribution is given in figure 8. Figure 9: Error distribution for random mesh generation. Levels 6,7 and 8 respectively.

Random mesh generation

To check the robustness of the scheme ruling out any possibility of error cancellation due to the regularity of the mesh, we applied a random algorithm to generate the grid, see Fig. 9). The mesh is then subsequently refined.

The convergence order of the method is given in Table 3.

Dirichlet boundary conditions

Boundary conditions on the interior subdomain are imposed by a penalty term, see equation ( 3). We consider the same domain and exact solution u e (x 1 , x 2 ) = sin (x 1 -0.5) 2 + (x 2 -0.5) 2 as in the previous section. The solution is penalized on all the mesh nodes lying inside a centered cylinder with radius equal to 0.25 with the value at the cylinder boundary. Equation ( 3) is thus solved with ε = 10 -11 and u 0 = sin (0.25) 2 + (0.25) 2 . The grid is subsequently refined in a graded way according to the distance function Φ to the cylinder in a layer |Φ(x)| ≤ 0.2. The error distribution in the computational domain for tree level 7 is presented In figure 10 Figure 10: Error distribution for the penalized cylinder with a maximum tree level 9 and 7 respectively.

Uniform refinement and AMR for a multiscale problem

We investigate an idealized multiscale problem with the same domain and exact solution as in previous sections, but we now we consider a penalized centered cylinder with radius equal to 0.01. Equation ( 3) is now solved with u 0 = sin (0.49) 2 + (0.49) 2 and ε = 10 -11 . The grid is refined according to the distance to the cylinder. The error distribution on the whole domain is presented in figure 11 while a zoom around the cylinder is presented in figure 12.

In what follows we compare the results obtained with our quadtree approach (AMR) to the results obtained with Cartesian uniform grids. The Cartesian results are obtained with the standard five-point stencil for the Laplacian operator with two different orderings: the Z-order (UZ) and the classical (i, j) order (US). The Laplace operator for the US ordering has a penta-diagonal structure while a more disperse structure is obtained for the UZ ordering. The non-uniform grid is obtained by mesh refinement near the cylinder with four levels of jumps between the maximal and the minimal depth of tree, enforcing balancing constraints through faces. In each case, the uniform grid is chosen to obtain the same degree of error than that obtained with the corresponding quadtree grid (see table 5). Since maximal error is located near the cylinder boundary (first order penalization, see figure 12), the cell size for the uniform mesh is equal to the smaller mesh cell for the corresponding AMR quadtree grid. A comparison of the total number of points used for the uniform and quadtree grids is presented in table 6. At level 15, the AMR grid has approximatively 220 times less grid points. The uniform grid is chosen so that infinite norm of the error is almost equal to that obtained with the corresponding quadtree grid. An intersecting consequence is that the L 2 norms are also equivalent whatever the mesh used. It is thus not necessary to use a fine mesh in the whole domain. The slight differences between US and UZ errors are a consequence of the ordering that has an influence on the linear solvers used. The CPU time required to solve the linear system is reported in table 7. All the tests presented in this section have been solved using 96 cores on 4 nodes. The computational time needed for the AMR are one to two orders of magnitude smaller compared to the US grid. The computational time to solve the linear system for the same uniform grid can be significantly larger for the UZ ordering than that for the US Cartesian ordering. The Krylov space used for this test is BCGS with ASM preconditioning and ILU sub-preconditioner.

The results of this section strongly depend on the configuration studied, i.e. the ratio between the square size and the cylinder diameter. On the one hand, even though Z-order may significantly reduce performance of linear solvers, the number of grid points can be reduced to an extent that makes the solution by far faster. On the other hand, if one is interested in solving a linear system (at least a Poisson equation) for a non multi-scale problem, the Cartesian grid with the usual Cartesian ordering is the most efficient approach.

Tree

L 2 L ∞ L 2 L ∞ L 2 L ∞ Level

Diffusion coefficient discontinuity

We consider now the full problem given by equations ( 1). The diffusion coefficient κ(x) is considered to be piecewise constant: We are thus interested in approximating the solution of the following system:

κ(x) = 1 if x ∈ G, 100 if x ∈ S.
κ(x)∆u(x) = -1.0 in G ∪ S, (5a)
[κ(x)∂ n u(x)] = 0 on γ, (5b)
The whole domain under consideration is the unit square [0, 1] × [0, 1]. The interface γ separating subdomains G and S is defined by the circle with radius equal to R = 0.25 centered at (0.5, 0.5). The subdomain S is inside the leading disk. The analytical solution considered is defined by:

u(x, y) = 1 8 - 1 4κ G (x -0.5) 2 + (y -0.5) 2 in G, (6) u(x, y) = 1 8 - 1 4κ S (x -0.5) 2 + (y -0.5) 2 - R 2 4 1 - 1 κ S in S. (7)
The coefficient κ is regularized with equation ( 4) where parameters α, β and σ are chosen such that:

α + 1 2 (β -α) = 49.5 + 1, β -α 2 = 49.5, σ = 100.
In what follows two classes of mesh refinements, called AMR1 and AMR2 are used.

AMR1:

The first class of meshes used are refined near the mollification region around the interface γ with the following criteria:

• the maximal depth of the tree is fixed at value from M = 7 to M = 13;

• the squared domain is initially uniformly meshed with level M -4;

• from M -4 to M the mollified function ( 4) is evaluated on each octant.

If the octant lies on the regularization zone3 it splits in four children;

• balance constraints are applied on the jump zones.

Examples of this kind of meshes are presented in figure 15. The corresponding convergence results are presented in table 8.

AMR2:

The second class of mesh refinement follows the criteria:

• the maximal depth of the tree is fixed at value from M = 7 to M = 13;

• the squared domain is initially uniformly meshed with M = 7 (16384 octants); • from 7 to M the mollified function ( 4) is evaluated on each octant. If the octant lies on the regularization zone it splits in four children.

• balance constraints are applied on the jump zones.

Figure 15: Zoom on the AMR1 grids for levels 7 and 8. As expected, for both mesh refinements the overall error is distributed near the mollification region. The mesh can thus be relaxed outside the mollification region allowing to save CPU costs (time and memory). Compared to the balanced case, for given error level, we have here about 5 times less grid points.We study the same configuration described in the previous section but without the 2:1 balance constraint. An example of the unbalanced (4:1) grid is given in figure 17. Mesh convergence results are reported in table 10. The error distribution on the entire domain presented in figure 19 is comparable to the error obtained on balanced meshes for the same problem.

Figure 19: Mesh referring to table 11. Error distribution.

Three-dimensional problems

The extension of the numerical approach to 3D problems is quite straightforward. The number of the constraints to be satisfied for a consistent set of weights is 10 in 3D (6 in 2D). The numerical approach is still natively parallel.

Validation

This section is devoted to study the convergence error of our approach for 3D problems. We consider a sinusoidal solution centered in the cube [0, 1] × [0, 1]×[0, 1]. One level of 2:1 mesh refinement is performed inside a fictitious sphere with radius equal to 0.15 centered in the computational domain.

Initially, the exact solution considered is u e (x, y, z) = sin((x -0.5) 2 + (y -0.5) 2 ). It is invariant along the z-axis to check the 2D symmetry of the solution. Figure 20 shows the matrix structure for 36128 grid points. The matrix presents several sub-blocks of non-zeros values coming from the Z-ordering. Note that the matrix structure is significantly different when a classical Cartesian ordering is used, even if no refinements are considered. Because of this, like in the 2D case, for the same number of grid points the computational time required to solve the linear system will be higher using the Z-ordering compared to the classical Cartesian ordering. Computational efficiency will be recovered since for given error, a significantly smaller resolution will be required. An error map on a cross section is presented in figure 21. As expected, the error is concentrated in a narrow band around the fictitious sphere where refinement is performed.

Let ∆ h be the discretized laplacian operator and u e the exact solution on mesh centers. The convergence order of the residual is computed as if the mesh were uniform: p = 3 * ln(err 1 /err 2 ) ln(np 2 /np 1 ) , where err stands for error norm and np the total number of points. A convergence analysis of the residual ∆ h u a -f is presented in table 12. Second-order accuracy is obtained for the infinite norm. A map of the residuals in several cross sections is presented We now increase the level of jumps on a balanced mesh from one (previous example) to three. The error results are presented in table 13. A secondorder accuracy is almost reached for both the L 2 and L ∞ error norms. The distribution of the errors is presented in figure 23 for a mesh refinement with level 9 inside the sphere and 6 outside.

We now consider a 3D exact solution: u e (x, y, z) = sin((x -0.5) 2 + (y -0.5) 2 + (z -0.5) 2 ). The results in terms of error norms are reported in table 14. The distributions of the error on the sphere and in a cross section without the sphere are presented in figure 24. A second order accuracy is obtained, and a symmetry on the error distribution is observed.

Random mesh generation

We applied a random algorithm to generate an arbitrary grid also for the three dimensional extension, see Table 13: Laplacian resolution with AMR in a sphere. Balanced mesh, three levels of difference between maximal and minimal depth, 2D sinus analytical function.

method is given in Table 15.

Figure 23: Distribution of the errors for a mesh refinement with level 9 inside the sphere and 6 outside for 2D u e (x, y, z) = sin((x -0.5) 2 + (y -0.5) 2 ). For the first test case, the error distribution in a cross section is presented in figure 26. The error is minimal near boundaries where the solution is explicitly imposed. Errors are presented in table 16. As expected for an exact penalization on the sphere interior, a second order accuracy is reached.

L ∞ L 2 Mesh Points Order L ∞ Order L 2 3.9367e-

Conclusions

A cell-centered finite-difference method to solve Poisson equation on hierarchical Cartesian meshes is proposed. The main idea is to minimize the local second-order truncation error coefficient by an appropriate choice of the discretization weights. In order to reduce communications, the stencil involves only the direct neighbours, i.e. all the cells that are in contact (with face, edge or corner) with the cell under consideration. The data structure is based on a linear octree and it is intrinsically parallel. Error analysis in two and three dimensions shows that this scheme is consistent with second-order accuracy. For multiscale problems, this approach outperforms uniform parallel Cartesian solvers since significantly less discretization points are needed. Even if most of the examples presented in the paper deal with graded grids, it is shown that the scheme can be applied to non-graded grids without any modifications.

Figure 1 :

 1 Figure 1: Sketch of the domain under consideration.

Figure 2 :

 2 Figure 2: A square decomposition and the corresponding quadtree.

Figure 3 :

 3 Figure 3: Global nested Z-ordering example.

Figure 4 :

 4 Figure 4: Example of bijective key construction.

Figure 5 :

 5 Figure 5: Discretizarion grid of the Laplacian in c 4

Figure 6 :

 6 Figure 6: Uniform mesh configuration. The weights are enumerated following the Z-Order.

Figure 7 :

 7 Figure 7: Example of the mesh configuration for level 4 and 5.

Figure 8 :

 8 Figure 8: Example of error distribution on a grid corresponding to level 6.

Figure 11 :

 11 Figure 11: Error distribution on the whole domain for the penalized cylinder with radius equal to 0.01.

Figure 12 :

 12 Figure 12: Zoom on the error distribution around the penalized cylinder with radius equal to 0.01.

Figure 13 :

 13 Figure 13: Resolution time trend.

Figure 14 :

 14 Figure 14: Numerical result obtained by AMR, superposition of analytical and numerical solution plane section, with a projection of the error and a representation of the mollification (grey part).

Figure 16 :

 16 Figure 16: Zoom on the AMR2 grids for levels 8 and 9 and 13.

Figure 17 :

 17 Figure 17: Error example, level 8, sinus analytical function.

Figure 20 :

 20 Figure 20: Structure of the 3D matrix for the Laplacian operator with 2:1 graded grid (36128 points).

Figure 21 :

 21 Figure21: Error map on a cross section for u e (x, y, z) = sin((x -0.5) 2 + (y -0.5) 2 ) with 2:1 refinement in a sphere.

  Figure 22: Representation of the residuals for the 3D Laplace operator in several cross sections.L ∞ L 2 Mesh Points Order L ∞ Order L 2 2.41187e-04 1.16224e-04 4880 --7.93562e-05 4.16123e-05 32656 1.755 1.6184 2.20059e-05 1.23492e-05 264944 1.837 1.7461 5.82872e-06 3.36007e-06 2111880 1.919 1.8813 1.50078e-06 8.76136e-07 17103976 1.947 1.9281 3.8073e-07 2.23642e-07 137484026 1.976 1.965

Figure 26 :

 26 Figure 26: Error distribution in a cross section for the 3D penalized sphere test case.

Table 2 :

 2 Error norms and order of the scheme.

	Tree level	L ∞	Order	L 2	Order
	4	5.02265e-04		2.49066e-04
	5	9.92104e-05 2.5315 4.96958e-05	2.506
	6	2.23894e-05 2.2155 1.13086e-05 2.19725
	7	5.36436e-06 2.087 2.72476e-06	2.075
	8	1.31696e-06 2.0365 6.70944e-07 2.0305

Table 3 :

 3 Convergence order for the random mesh generation. The first line involves 787 degrees of freedom, the last one 3223552.

	Tree level	L ∞	Order	L 2	Order
	6	1.18078e-04	-	7.37138e-05	-
	7	2.93059e-05 2.010 1.94914e-05 1.929
	8	6.40356e-06 2.194 4.3646e-06 2.159
	9	1.52669e-06 2.068 1.02794e-06 2.086
	10	3.72553e-07 2.035 2.48591e-07 2.048
	11	9.20017e-08 2.018 6.10625e-08 2.025
	12	2.28589e-08 2.01 1.51279e-08 2.013

Table 4 :

 4 Numerical results for the penalized cylinder.

	Tree level	L ∞	Order	L 2	Order
	5	1.39209e-02		3.21637e-03
	6	7.16906e-03 0.971 1.50085e-03 1.071
	7	3.84769e-03 0.932 7.15689e-04 1.048
	8	1.95191e-03 0.986 3.68745e-04 0.970
	9	9.72571e-04 1.003 1.56265e-04 1.18
	10	4.88266e-04 0.996 7.96255e-05 0.981

. Numerical results are reported in table 4. As expected, since the internal Dirichlet boundary conditions are not exactly imposed on the cylinder boundary, the maximum errors are observed near the cylinder boundary and the numerical solution is only first order accurate.

Table 5 :

 5 Errors obtained with a quadtree structure (AMR with four jumps of level) and with uniform grids for two different orderings (natural Cartesian, US, and Z-ordering, UZ). The size of the uniform grids is chosen to obtain similar errors with respect to the quadtree case.

		US	US	UZ	UZ	AMR	AMR
	7	5.25e-06 3.49e-05 9.30e-06 5.72e-05	-	-
	8	4.15e-06 2.79e-05 1.31e-06 1.29e-05	-	-
	9	8.96e-07 9.20e-06 2.62e-06 1.81e-05	-	-
	10	9.56e-07 9.09e-06 1.08e-06 1.08e-05 3.63e-06 1.07e-05
	11	6.57e-07 5.75e-06 7.71e-07 8.01e-06 7.47e-07 7.99e-06
	12	3.7e-07 4.16e-06 3.05e-07 2.87e-06 2.08e-07 2.87e-06
	13	1.64e-07 2.05e-06	-	-	1.08e-07 1.49e-06
	14	6.36e-08 9.34e-07	-	-	5.58e-08 7.33e-07
	15	1.13e-08 3.26e-07	-	-	1.16e-08 3.81e-07
			Tree Level	US/UZ	AMR
			7	16384		-
			8	65536		-
			9	262144		-
			10	1048576	4900
			11	4194304	19012
			12	16777216	76036
			13	67108864	302776
			14	268435456 1214512
			15	1073741824 4863616

Table 6 :

 6 Comparison of the number of points for the quadtree (AMR) and uniform (US/UZ) grids.

Table 7 :

 7 Comparison of the computational time (in seconds) required to solve the linear problem for the quadtree (AMR) and uniform grids (US and UZ).

	Tree Level	US	UZ	AMR
	7	3.5329e-02	8.2994e-02	-
	8	2.6406e-02	2.9260e-01	-
	9	6.5642e-02 1.8123e+00	-
	10	5.1011e-01 1.7149e+01 3.7959e-02
	11	3.7639e+00 2.0778e+02 1.1091e-01
	12	2.8374e+01 2.3868e+02 4.1040e-01
	13	1.9036e+02	-	2.4283e+00
	14	1.2410e+03	-	2.2296e+01
	15	7.6472e+03	-	2.7102e+02

Table 8 :

 8 Convergence results for AMR1.

	Tree Level	L ∞	L 2	Mesh Points
	7	2.40592 -02 1.69446e -01	3784
	8	2.43815e -02 1.73977e -01	14968
	9	3.86077e -02 2.77852e -01	51472
	10	1.86597e -02 1.34336e -01	112684
	11	2.87779e -03 1.98544e -02	228484
	12	6.60242e -04 3.82096e -03	465028
	13	1.54341e -04 1.02991e -03	1124968

Table 9 :

 9 Convergence results for AMR2. Examples of this kind of meshes are presented in figure 16. The corresponding convergence results are presented in table 9.

	Tree Level	L ∞	L 2	Mesh Points
	7	2.62959 -02 1.89502e -01	16384
	8	2.56705e -02 1.84833e -01	30868
	9	3.90077e -02 2.81516e -01	59896
	10	1.88669e -02 1.36216e -01	117796
	11	2.90886e -03 2.01399e -02	233512
	12	6.60242e -04 3.82096e -03	465028
	13	1.53515e -04 1.02783e -03	1090300

Table 10 :

 10 Circular Unbalance. Sinus solution, first level 6.

	L ∞	L 2	Mesh Points Order L ∞ Order L 2
	0.00138827	0.00682539	796	-	-
	9.97279e -05 0.000550322	3352	3.663	3.503
	2.73791e -05 0.000159641	13588	1.846	1.764
	7.78934e -06 4.55914e -05	54268	1.815	1.832
	1.95523e -06 1.14128e -05	217936	2.032	2.027
		Figure 18: Zoom on the unbalanced grid.
	A zoom of the unbalanced part is presented in figure 18.

Table 11 :

 11 Unbalanced AMR. First case level 7.

Table 12 :

 12 Study of residual order.

	Order

Tree depth level

∆ h u a -f ∞ Mesh Points

Table 14 :

 14 Laplacian resolution AMR in a sphere. Balanced mesh, three levels of difference between maximal and minimal depth. u e (x, y, z) = sin((x -0.5) 2 + (y -0.5) 2 + (z -0.5) 2 ).

	04 1.97745e-04	4880	-	-
	1.25677e-04 7.14724e-05	32656	1.802	1.61
	3.54814e-05 2.12077e-05	264944	1.812	1.74
	9.42605e-06 5.77689e-06	2111880	1.916	1.878
	2.42823e-06 1.50647e-06	17103976	1.945	1.935
	Tree level	L ∞	Order	L 2	Order
	4	2.55285e-02	-	6.53591e-04	-
	5	4.78024e-03 2.42 1.90869e-04 1.776
	6	9.45935e-05 2.337 4.51667e-05 2.079
	7	2.52537e-05 1.905 1.28204e-05 1.818
	8	6.53981e-06 1.949 3.39493e-06 1.916

Table 15 :

 15 Convergence order for the random mesh generation. The first line involves 736 degrees of freedom, the last one 1573888.

Table 16 :

 16 Numerical errors and convergence for the second order penalized sphere.For the second test case, corresponding to usual penalization, the error distribution in a cross section is presented in figure27. The error is maximal near the internal boundary. Errors are presented in table 17. The first order penalization is recovered. Figure 27: Error distribution in a cross section for the 3D penalized sphere test case.

	Level	L ∞	L 2	Mesh Points Order L ∞ Order L 2
	6	0.000238244 0.000106971	2976	-	-
	7	7.45466e-05 3.94184e-05	10536	2.757	2.369
	8	2.43216e-05 1.19565e-05	55672	2.019	2.15
	9	5.37193e-06	3.0825e-06	380024	2.359	2.117
	10	1.38687e-06 8.05033e-07	2826104	2.021	2.007
	11	3.52385e-07 2.05731e-07	21907208	2.012	1.999

Table 17 :

 17 Numerical errors and convergence for the first order penalized sphere.

http://www.optimad.it/products/bitpit/

https://www.mcs.anl.gov/petsc/

The regularization zone is defined by |∇κ(x)| > ε, where ε is a small parameter, here 10 -3 .

Acknowledgement: Experiments presented in this paper were carried out using the PLAFRIM experimental testbed, being developed under the Inria PlaFRIM development action with support from Bordeaux INP, LABRI and IMB and other entities: Conseil Régional d'Aquitaine, Université de Bordeaux and CNRS (and ANR in accordance to the programme d'investissements d'Avenir (see http://www.plafrim.fr/).

Penalization

We consider two test cases. The first one is the exact penalization, i.e. the exact solution is imposed on each node lying inside the centered sphere with radius equal to 0.05 by a penalty term. In the second one, the exact solution of the sphere boundary (that is constant for the solution under consideration) is reported on each nodes inside the sphere. The mesh is recursively refined in a narrow band around the sphere boundary.