Pierre-Jean Benghozi

Gilles Brégant

Bernard Celli

Wassim Chourbaji

Eric Fournier

Andreas Geiss

Guillaume Lebrun

Antonio Nicita

Antonio Perrucci

Antonio Sassano

Richard Womersley

They provided support, insight, expertise and challenges that greatly assisted at various stages of the research, Any errors are our own and should not tarnish the reputations of these esteemed persons. A special thank you to Martin Sims and the PolicyTracker team, Dan Craft at Forum Europe in Brussels and Gildo Campesato at Corriere delle Communicazioni in Rome who offered an invaluable public forum for

EXECUTIVE SUMMARY

Increased competition in telecommunications services in the past two decades has generated considerable benefits for Europe's citizens, consumers, industry and governments. More recently concern has grown regarding the relatively slow pace of 4G network deployment and fears that delays could be repeated with 5G. This paper analyses the role spectrum assignment policies have played in this mixed picture and concludes that the design of spectrum awards in a 5G context should evolve to place more emphasis on promoting infrastructure deployment.

Examples of policy decisions impacting market outputs are used to support our argumentation with evidence drawn from recent in-depth studies and examples covering the main European markets. These suggest it is time to re-evaluate whether the amount of revenue raised should be the overriding measure of spectrum auction success, and whether auctions on fees are the most effective means of promoting competition and driving investment.

We survey the analyses of causal relationship and trade-offs between various assignment methods and fee structures and conclude with considerations and guidelines for more effective and balanced spectrum assignment designs. As EU regulators consider reforms in this area the key challenge is how to align award processes with broader economic and societal objectives. We hope our paper can make a constructive contribution in this respect 1 .

SPECTRUM ASSIGNMENT DESIGN SHOULD BETTER ALIGN WITH PUBLIC POLICY OBJECTIVES AND INDUSTRY

STRATEGIES

This paper explores forward looking spectrum assignment scenarios that can better balance the requirement to efficiently use a limited public resource, with the equally important objective of maximising the economic and social benefits that can flow from investments in mobile network infrastructure. Our hypothesis is that by establishing the right incentives for Mobile Network Operators (MNOs) to fully exploit the potential of future network technologies today, the thresholds of infrastructure-based competition can be extended to fulfil the economic, social and industrial objectives of tomorrow.

The paper sets out some key overarching considerations regarding spectrum assignment for 5G and related technologies and services. It concludes that the principles that governed spectrum assignment in the last century and the beginning of this may no longer be fully valid and should be re-visited. We explore new approaches that better suit emerging technological, economic, and business realities and propose a re-balanced, optimised approach to spectrum licensing that can drive deployment of pervasive highquality networks. We then analyse trade-offs and suggest guidelines to steer policy decisions in crucial markets.2 2 SUB-OPTIMAL SPECTRUM ASSIGNMENTS DELAY NETWORK DEPLOYMENT Twenty years of sub-optimal spectrum assignment has resulted in delays in network deployment. It is vital that spectrum auctions rely on sound and not misleading assumptions. Spectrum economics has suffered from its positioning at an abstract, nonfalsifiable theoretical level. As illustrated by recent research, its conceptual reasoning, assumptions and expected outcomes are ill-suited to real-world applications and have been largely contradicted by industry developments. The appropriate approach to public resource management tells us that the radio spectrum as a public resource has to be managed in the public interest.

AUCTIONS ON FEES ARE NOT A PRE-REQUISITE FOR COMPETITION IN MOBILE COMMUNICATIONS

In the last decades of the 20th century the widespread view was that the promise of breakthroughs in communications technologies were being hindered by the powers of legal monopolies, and that competition had to be introduced into the industry. In mobile communications, spectrum limited availability dictated that competition had to be managed ex-ante and the number of licensed operators had to be predetermined by governments and National Regulatory Authorities (NRAs). To overcome the apparent limitations of administrative procedures in selecting the competing licensees, auctions were adopted following the U.S.A.'s successful example in 1994. They were considered more transparent, quicker, and removed the need for governments to pick winners. Ronald Coase's seminal 1959 paper advocates that spectrum assignment should be based on market and pricing mechanisms, where property rights are assigned with the objective of maximising output from a scarce resource. Its logic helped open the telecommunications industry to competition and brought about a change in business culture and practices. The belief that "market mechanisms" in spectrum management were an optimal means of solving assignment problems and promoting the industry and the economy was widely shared, and delivered the communications revolution we all benefit from today.

Over the last two decades, spectrum policy has been widely governed by the same highlevel, generic, economic principles, summarised as follows:

A. Auctions are the optimal mechanism not only to determine a spectrum price but also to align private and public objectives, as by actively bidding, operators demonstrate their willingness to invest in network deployment. B. By licensing a public resource, governments should aim to maximise the price, or, more correctly, to use market mechanisms to determine the amount paid by buyers that balances supply and demand of radio frequencies.

Principle A is based on the fundamental Econ 101 3 assumption that market mechanisms consistently provide the optimal outcome. However, evidence suggests that potential shortcomings with this assumption abound in relation to the deployment of communications networks. Governments and NRAs have waged an ongoing fight against natural monopoly resurrection tendencies. Moreover, competition alone has not been sufficient to achieve specific public policy objectives. Almost all countries have taken measures to complement market mechanisms and provide public policy defined levels of services not only in rural, low-density areas, but also in many urban districts, with even some single streets in big cities having been designated as "market failure areas"4 .

Principle B applies Econ 101 to the use of public resources. It is a bold assumption that for the state to handle public funds optimally, it must behave as a private agent in the management of its assets. This argument has a strong element of opportunism at a time when tight government budgets are badly in need of income. The evidence, however, shows that discrepancies arise between misguided public policies in spectrum assignment and the realisation of public objectives in industry and market growth.

The high-level argument that auctions are an effective process to select those operators that can use the frequencies most valuably is an accessible one, and as hard to verify as it is to falsify. But once the assumption is accepted (Econ 101), the higher the fee, the "better" the performance not only for the assignment itself but for the development of the industry. Spectrum auction studies in the first decade of the 21 st century have failed to address what they were meant to research, i.e. the impact of spectrum assignment design on industry development, competition, and contribution to overall economic growth. The means have superseded the aims, and a "successful" auction in the literature has been taken as one achieving high fees rather than positive social returns. The tendency of licensing through auctions to be used as a tool for influencing market design and structure rather than acting as a neutral and invisible hand, has also been largely ignored in the literature.

Ironically, the growing popularity of spectrum auctions took place at a time when once triumphant Econ 1015 was being abandoned, or at least side-lined in most areas of applied economic analysis. With the current generation of economists, general market equilibrium considerations and the reliance on generic micro-economics have lost ground to careful analysis of specific concrete market situations 6 . Over the last two decades we have witnessed a growing emphasis on applied economic analysis with an increased focus on economic realities and a move away from high-level non-falsifiable theories. This is now also happening in the debate on mobile industry economics. Spectrum economics has lagged in this respect but is now catching up and several recent studies on the outcomes of spectrum assignments provide a better, pragmatic view of the results of auctions.

STUDIES SHOW SPECTRUM AUCTIONS HAVE NOT DELIVERED THE BEST POSSIBLE BENEFITS FROM MOBILE

Governments have been increasingly dissatisfied with the network coverage achieved with first 3G, then 4G, and are now concerned by uncertainties surrounding 5G business models. They have faced "…widespread public dissatisfaction around coverage, particularly outside urban areas." (Ofcom, 2016 7 ). However, in a classic example of the right hand ignoring what is being done by the left hand, some branches of government, or agencies in charge of licensing, have tended to focus exclusively or primarily on maximising the fees they can derive from the spectrum auction procedures. Only secondary attention is being paid to the now widely observed limitations of this policy tool in achieving broader policy objectives. This is especially damaging at a time when availability of solutions such as 5G are vital enablers for the fourth industrial revolution and will confer lasting competitive advantages to regions that are early adopters. While Europe may drive the design and architecture of advanced connectivity solutions, North America and North-East Asia are expected to take early leads in 5G deployments and adoption. 8 European policy makers need to take appropriate action to redress this balance.

Recent studies suggest that the conventional approach to licensing spectrum has not achieved connectivity policy objectives. There is a growing body of evidence that spectrum auctions in their current configuration not only fail to stimulate network investments, but also hinder them.

In their (2017) paper 9 The effects of spectrum allocation mechanisms on market outcomes: Auctions vs beauty contests, Kuroda, Toshifumi, Baquero Forero, Maria Del Pilar, compare the evolution of market outcomes in 47 countries after the assignment of mobile spectrum by auctions and beauty contests held from 2000 to 2008: "Traditional auction theory predicts the merits of auction versus "beauty contests".…. We employ two semi-parametric estimators to determine the treatment effects and find that 3G mobile phone penetration rates among auctioning countries are 1.04-8.95% lower. Findings suggest that auctions used to raise public revenues not only transfer profits to the government but also sacrifice consumer surplus".

A research report 'Effective Spectrum Pricing' by GSMA and NERA (2017) concludes10 : "Statistical evidence shows the impact on consumers and links high price outcomes (in auctions) with:

• Lower quality and reduced take-up of mobile broadband services;

• Higher consumer prices for mobile broadband data;

• Consumers losing out on economic benefits with a purchasing power of an estimated US$250 billion across 15 countries where spectrum was priced above the global median -equivalent to US$118 per person"; • Lower spectrum input costs are linked to greater price competition and higher usage"11 .

A study by PolicyTracker, LS Telcom & VVA (2017) for the European Commission12 finds that "the grouping with the highest auction prices also had the poorest network availability. This questions the common view that operators who pay high prices for spectrum must invest in their networks to make this money back." Countries where operators have paid the most for spectrum over the past decade, showed the worst 4G network availability13 .

Cambini & Garelli 14 (2017), in research covering 24 countries in the period 2005-2014, found that spectrum fees and availability do not have a significant impact on operators' revenue and investments. "The analysis provides evidence that spectrum availability and fees are not significantly correlated with mobile industry revenues suggesting that market expectations to extract additional revenues from the mobile service following new spectrum auctions are likely not to be respected." This would indicate that spectrum fees are treated as sunk costs by operators and therefore have no impact on investment and pricing decisions, thus voiding the incentive role of auctions on investments.

Finally, Hazlett and Munoz (2012) demonstrated that efficiencies associated with retail services in mobile markets are about 240 times as large as those associated with licence revenues 15 .

These empirical studies confirm the analytical assumptions by Pogorel & Bohlin (2017) that spectrum auctions aimed at high spectrum fees do not serve to stimulate investments and network deployment16 .

It is now clear at both conceptual economic analysis and empirical levels that local market mechanisms in the form of spectrum auctions do not align with industry development objectives. Public policy objectives, which are central to the issue of non-discriminatory access to spectrum, have only partially been achieved. Some reprioritising of business profitability, budget objectives, and public policy defined social impact is required.

Although most industry and government representatives recognise those facts when discussing behind closed doors, only a few have chosen to publicly recognise these shortcomings and urge better practice. Budget considerations are understandably high among government priorities, especially in countries with significant public debt.

PRIORITISING REVENUES IS AN UNDERSTANDABLE AND VALID POLITICAL CHOICE, BUT IT IS TIME TO RECONSIDER AND REBALANCE ASSIGNMENT OBJECTIVES

Growing budget deficits have contributed directly to the attractiveness of auctions as a means for governments to assign spectrum. Indeed, some have bent over backwards to justify spectrum auctions with the French government, for example, declaring in 2015 that the proceeds of their 700 MHz auction would be allocated to defence spending. This consideration played a determining role in shaping not only spectrum assignment design but also the conditions of network deployment.

While revenue raising is an understandable and valid political choice, it comes with its own costs in terms of deprioritising other broader economic and social perspectives. This over-focussing on revenues does not seem to be consistent with the broader range of spectrum policy objectives cited by NRAs in their publicly available mission statements (see Annex 6.2 for summary).

These mission statements demonstrate the breadth of policy objectives targeted by spectrum policy including competition and economic and social objectives. Further research into the nuances between different NRA statements and focus in this regard would be useful in order to explore the options for more consistency in policy choices across Europe.

One difficulty, of course, is that social and economic impacts, whatever the efforts recently devoted to analysing them, can be conceptually and practically hard to precisely measure and quantify17 . If all the growth percentage points supposed to derive in the last three decades from computers, networks, and digital progress in general, were aggregated, our economies would fly at space shuttle speeds. However, it is easier to quantify the objectives in terms of coverage and deployment schedules that are explicitly defined in the assignment procedure.

It may be that we will see increasing tensions between NRA positions on coverage and certain government departments' focus on revenue. There is also scope for growing divergence between government ministries, with for example, finance and regional development departments promoting contrasting views on whether to prioritise revenue maximisation or deployment.

Overall it is important to emphasise that there are choices to be made and that spectrum assignment procedures can be effectively designed to deliver on these choices.

REVISITING SPECTRUM ASSIGNMENT -GUIDING PRINCIPLES

Competition is rightly at the heart of telecommunications industry dynamics with competitive bidding between firms central to effective assignment processes. It can effectively deliver on agreed policy objectives if assignment design focuses on investment and deployment objectives.

As governments and regulatory authorities design future spectrum assignment procedures, there are a number of important elements that need to be systematically assessed. In this section we explore areas where fresh thinking and innovation are required.

ARTIFICIAL SCARCITY

Efforts to ease spectrum supply constraints are the priority. The spectacular rise of mobile use, the drama surrounding assignment processes, and the high levels of frequency fees, should not blur the big picture. Allocation across the world remains mostly a technical process managed by highly competent specialised agencies at international, regional, and national levels. Any spectrum manager, however, cannot help but think that auction fee levels are demand driven and would be lower if the supply was less limited.

Whether this can be achieved through improved government and market player strategies, by dynamic spectrum access technology advances, by sharing, or through financial incentives is an open question which deserves intense scrutiny. Some believe that spectrum management reform can ease the problem of spectrum scarcity. For market mechanism advocates, the solution lies in generalised trading and incentive auctions. For technology enthusiasts, it is open, dynamically allocated, shared and unlicensed spectrum. All of these approaches will have a role to play in easing the shortage but artificial scarcity will remain a significant issue.

TECHNICAL EFFICIENCY

The primary imperative of spectrum assignment is the efficient use of the spectrum. For 5G to be efficiently implemented, the spectrum implications of 3GPP 5G specifications have to be followed. In terms of spectrum, to quote Digital Europe18 : "…3.4-3.8 GHz is essential for 5G deployment… it is paramount to clear and defragment this band to enable contiguous ~100 MHz bandwidth per operator". Even wider channels, possibly 400 MHz to 800 MHz, are needed in the mmWaves.

OPEN SPECTRUM LICENCES: ACCESS, SHARING, TRADING, AND LEASING

A key consideration for decisions to be taken by late 2018 and 2019 is what makes 5G different, not just an enhanced version of the previous wireless technology generations. 5G might and should provide the opportunity and possibility for new developers to offer services of various dimensions, local, regional or extended, industry-specific or crossindustry, as either operators, virtual operators, or service providers.

"Opening" spectrum licences is a crucial debate for 5G technology. Business developers, potential new entrants like verticals, and service providers to the verticals, are expected to be part of the future 5G ecosystem.

Many regulators intend to assign spectrum for 5G in the forthcoming months. At this time, most innovative business cases for 5G technologies will still be in a development stage, some of them by non-MNO industry actors. Those non-MNO actors either are still not ready to apply for spectrum of their own or are confronting justifiable objections by regulatory bodies outlining the risks of spectrum fragmentation.

The current most likely outcome is that MNOs will apply for spectrum at every opportunity in order to secure frequencies for ever-expanding customer needs and to fend off potential new wireless services providers. In this context, we must, however, ensure the licences remain "open", allowing for future sharing and flexible spectrum access modes. Implementing such provisions is very sensitive: does this translate into mandatory wholesale provision or MVNO like obligations? Such a clause might entail sharing regulation, and wholesale services rates control.

LICENCE DURATION

Extended licence duration has been advocated by powerful voices from both operators and the European Commission. This is based on the consideration that an extended investment horizon can drive more investment 19 . Most national governments and many NRAs have resisted this move. To illustrate an NRA viewpoint, we can quote AGCom 20 :

"As regards the duration of the of use, as already explained in other similar tender procedures, the Authority considers that this duration should not be too short, in order to provide the successful tenderer with sufficient time to use the bands efficiently and recover the necessary investments. This also in order to increase the interest in the allocation of the frequencies in question and therefore the competitiveness of the tender procedure. At the same time, the duration cannot be too long, in order to allow the State, within a reasonable time, to be able to regain possession of the resource where necessary for the purpose of maintaining the efficient use of the scarce resource over time. Today, the cycles of technological development are increasingly rapid, as the accelerated framework of 5G development demonstrates, and it is, therefore, appropriate that the State may have, if necessary, the possibility of proceeding to a major band re-farming, for example allocate the asset to other use or other users. "

The debate on licence duration was particularly contested during negotiations on the European Electronic Communications Code (EECC), with the co-legislators finally settling on 20 years (15+5) minimum duration. Most importantly, governments and regulators should take account of the need for sufficient duration to correspond to investment cycles and to allow investors to recover their expenses and fully exploit their investments.

SPECTRUM VALUE

As our last consideration, let us make clear spectrum has no intrinsic value. Its value resides exclusively in the contribution its use makes possible for society and the economy.

Aligning public objectives and industry strategies is the essence of public policy. "Market mechanisms" work in market conditions. Further positive short-term and long-term impacts at telco, industry, government budget, and macro level are also considerations that must be embedded in the terms of the licensing process.

Operators will know precisely what is expected in the terms of their licence, allowing them to define their business model and strategy. The fee paid to the government should lose its central status and be considered as a normal counterpart of the use of spectrum resources.

SPECTRUM ASSIGNMENT DESIGN FOR 5G: ALIGNING PROCEDURES WITH ECONOMIC AND SOCIAL OBJECTIVES

Politicians are exerting increasing pressure on the industry to deliver on 5G's potential to underpin Industry 4.0, promote cross-industry digitisation, and provide the connectivity building blocks for the region's digital future. While the clear majority of spectrum auctions this century have included policy defined obligations related to coverage and deployment schedules, the financial bid has been the central determinant in granting the licence. The evidence highlighted in section 2 suggests this has delivered disappointing outcomes and there appears fresh momentum to explore innovations in assignment processes and conditions to address this.

The 2018 example of 4G licences renewal in France21 , extended terms of payment introduced in countries like Spain, Sweden, and India, and the possible abolition of fee maximisation in Colombia,22 are indications that something is beginning to give in the field of auctions. Japan endorsing a "comprehensive strategic approach for 5G spectrum", and the EECC formalising a role for the Radio Spectrum Policy Group (RSPG) to "peerreview" spectrum assignment procedures in the EU, shows that policymakers are perhaps willing to look at new, more dynamic approaches to spectrum assignment with a stronger focus on the following high-level objectives:

-Prioritising macro-economic benefits; -Preserving openness for long-term competition; -Reaping the benefits of possible major technological disruptions like dynamic spectrum access.

Given that spectrum is a limited public resource, we consider in this section the options facing policy makers, and assess their relative merits while addressing the following questions: What should be the public policy criteria governing spectrum assignment procedures to drive economic and social benefits and technology leadership? What approaches are needed to achieve deployment, coverage and social policy goals?

In particular we consider the practical implications, challenges and consequences of a rebalancing of assignment objectives in a 5G context. We group and review the main variables and parameters of spectrum assignment, highlighting how they relate to the defined objectives, and highlighting the trade-offs. Having accepted that auctions on fees are not the one and only way to 5G deployment, we can review the best options. Here we tentatively assess different assignment options based on their impact on network deployment according to experiences in previous rounds of spectrum assignment. We examine, in turn:

• Frequency fee auctions with improved coverage obligations;

• Negotiated deals on frequency assignments for coverage like the French 2018 "New Deal" on mobile coverage23 • Auctions on investment and coverage commitments.

OBLIGATIONS

Auctions with coverage obligations have been frequent in spectrum assignments in Europe: 25/25 assignments in the 800 MHz band and 12/23 in the 2.6 GHz band (Magi) [START_REF] Magi | Assessment of the socio-economic impact of mobile broadband auctions[END_REF] . Operators, however, have been placed in a difficult position. Most have strived to comply with their obligations but as we have seen previously, Governments have expressed expost dissatisfaction with network deployment outcomes and there remains considerable friction regarding timely and cost-effective access to sites. Consequently, the latest generation of assignment procedures has included more precise and stringent obligations and some governments are separately driving initiatives to lower deployment barriers. NRAs now have ample experience and have come up with many smart features in the design of the assignment procedures. Coverage obligations are increasingly common and accurately defined, as demonstrated by Ofcom in UK 25 , or BNetzA in Germany, and as featured in the recent case of Italy, which we can take as an example of efforts to rebalance assignment criteria 26 .

The main feature that stands out from the Italian planned coverage obligation is that it aims to ensure the coverage of all national households and 80% of the population within 36 months: There is a possibility of joint coverage by two operators, on the condition of 99.4% population coverage in 54 months from the release of the frequencies with cooperation possible among operators. Roads and railways are to be covered in 42 months with possibilities of roaming and pooling. 2400 tourist areas are to be covered in 66 months. It has turned out to be the unique case among EU member states in which an obligation was designed from the start to cover close to 100% of population 27 .

The focus of the assignment procedure is on coverage and network deployment. It can be defined as population and/or geographic coverage commitments or expressed in financial terms, as featured in a 2018 Danish award which came up with an interesting twist in the coverage/investment combination: "Winning bidders will have the option of bidding for extra coverage obligations in exchange for a reduction in their licence price" [START_REF] Telecompaper | Danish govt issues final rules for 700 MHz, 900 MHz[END_REF] . This scheme opens the possibility for the regulator to avoid the dilemma between pre-defined, and operator-defined objectives. It provides an interesting way for operators to adjust their investment objectives within an auction procedure.

NRAs have come up with innovative combinations. Unlike most other European NRAs, PTS 29 , in a 2011 700 MHz assignment, attached coverage obligation only to one of the six lots (the last one, FDD6), so that only one operator was obliged to meet the requirement. The DEA in Denmark is retaining the same asymmetric requirement in its 2018 procedures for the 700 MHz and 900 MHz band auction 30 .

Other defining elements in the assignments should be considered. Assessing the relationship between a specific frequency band and the network deployment are no different from the current situation. There will also be a need to account for different use cases: 5G in general, and IoT in particular, have different use cases, with distinct coverage requirements.

One approach which is sometimes considered, but rarely tested, is to put auction proceeds into a fund ("USO-type".) This fund could then be actively used, through public purchasing, to cater to prioritised societal and political needs including redundancy in networks, coverage in rural and remote areas etc. All, of course, subject to state aid controls. The model implemented in Sweden in 800 MHz and planned for 700 MHz is in line with this approach.

NRAs, based on their appraisal of the public interest, have opened auctions with dual objectives: combining 90-95% coverage conditions and a spectrum fee auction. By doing so, they entrust the bidders with a somewhat conflicting commitment. The payment of the fee will make it more difficult to invest in the network. This is a risk shared by the NRAs and the operators, but in the end, it can always be said that the fund devoted to the spectrum fee could have been put to better use allowing quicker deployment of the network. Alternatively, in cases like early stage 5G deployment, where technology and economic risks and uncertainties are high, certain NRAs might not want to pre-define coverage obligations. Possibly, the assignment mode would warrant from the bidders' substantial but more progressive investment steps. Coverage might be different for different frequency bands considering the technical complementarities, for instance between sub-1GHz bands and those above 3GHz.

NEGOTIATED FREQUENCIES-FOR-INVESTMENTS

In the ARCEP "New Deal" example, which covers the renewal of 4G licences, mobile operators are bound to an intensive and accelerated country coverage program. The ultimate impact of the plan will be more investment over the next three years than in the last fifteen. This approach has so far only been implemented in France, and partially in Sweden. The challenge of this approach is the competition angle. Is it a deal limited to existing licence holders, or are new entrants admitted to the negotiating table? How are they selected? To combine the competition imperatives with the "New Deal", a 2-stage process could be implemented:

-Select one or more new entrants through tender -Negotiate their investments.

AUCTIONS ON INVESTMENT AND COVERAGE COMMITMENTS

In auctions on coverage obligations, operators are in the driver's seat as the bidders' commitments are left to business strategy considerations. As opposed to auctions on frequency fees with coverage obligations, the pre-determined commitments of bidders are flexible. Unlike the negotiated frequencies-for-investment ("New Deal") model, the process is competitive from the start.

The objectives proposed by the bidders would presumably be expressed in quantitative terms, mirroring the political aspirations of connectivity, coverage, quality, and speed. The network evolution over the period under consideration will have to be articulated with investment plans and the duration of the licence (15+5 years according to the new EECC). To make the bids comparable, investments over time will be aggregated at present value, accounting also for the evolution of network costs.

For illustrative purposes, we have drafted in Annex 6.1 a summary application form inspired by recent assignment procedures but corresponding to the objectives set out in this paper. Article 5 of the form, which defines the bidding procedure, reads: "Those entitled to the use of the frequencies are identified, for each right of use, on the basis of rankings expressed by band and for the reserved lot, based on the objectives offered through a system of competitive improvements, according to the modalities established in the call for tenders, starting from a minimum level, established for each lot."

PRICING THE USE OF SPECTRUM AS LIMITED PUBLIC DOMAIN

In the investment centred assignment procedure, frequency fees do not play the central role. The assignment procedure, although investment-centred, must nevertheless determine what charges should be paid for the use of spectrum as a limited resource. What frequency fee should be paid to the government? We could consider various methodologies:

-% of investments/ deployment commitments; -% of expected income; pre-defined flat fee.

The terms of payment could be:

-Upfront; -Annuity instalments; -Spectrum annual fees.

Alternatively, and more radically, the spectrum fee could be waived or limited in order to favour investments. The government will benefit from increased incomes of citizens and all industries, and from the corresponding tax receipts over time. This focus on investments also has positive impacts on R&D, technology and standards.

The benefits from extended and accelerated network deployment will accrue to the public budget as well, through successful economic activities. To permit this expansion it will be increasingly important due for the public sector and local municipalities, to facilitate, and not hinder the necessary infrastructure deployment. 31 Ultimately CAPEX and OPEX amount to an investment equation: frequency fees, network deployment and coverage obligations of different natures, per frequency, per geography, and over time. The risks associated with the various dimensions of the business activities being developed add up a familiar investment calculus. Two factors can disrupt this: the reserve price set by the NRA in the auction, and the auction process itself, as we have witnessed with the slower than expected deployment of 4G.

In our sample application presented in Annex 6.1, Article 8 sets out how the spectrum fee is determined: "Successful tenderers are required to pay a frequency fee for the relative rights of use, as a contribution to the use of radio frequencies. Those are based on the pre-determined amount, affected by a coefficient 0<X<1 corresponding to the investment effort. The predetermined amount is defined by an international benchmark and an assessment of costs and profitability. Coefficient 0 corresponds to 100% deployment and results in no or minimal frequency fee. Coefficient 1, no coverage commitment results in full frequency fee. The winning bidders are required to pay the frequency fee produced at the end of the procedures. The payment of the bidder awarded is paid in instalments according to the procedures laid down in the call for tenders".

MONITORING AND COMPLIANCE

Another key issue is the compliance of bidders in the implementation of the deployment commitments in terms of coverage speeds, consistency, schedule, in their bids. A major risk is the potential divergence between ex-ante commitments and ex-post outcomes. While traditional auctions are based on ex-ante expectations including auction fees, the investment incentive auction design relies on carefully designed rules of behaviour and follow-up monitoring. To make sure that the investments the operators have promised are indeed taking place, institutional arrangements should be designed to ensure the compliance of connectivity outcomes to commitments and to cope with potential shortcomings.

One possibility is to put the investment proceeds in escrow to be released to match deployment by the operators. Sweden's PTS used this in 2011 and is considering it for 700MHz award process. Keeping investment funding in a fund, with adequate yield, would have the advantage of reversing the burden of the proof: it would be up to the operators to demonstrate they have complied with their commitments.

In the end, the task of monitoring the implementation of the selected licence holders will not be much different from what is currently performed by NRAs. It is indeed delicate, but NRAs have been dealing with it in many instances. Some flexibility should be allowed on investment plans given changing economic conditions. Coverage obligations should be fulfilled, and the present value of the scheduled investments maintained. A degree of flexibility of investments in specific bands is warranted: the commitments cannot be band specific over the extended period.

The issue of returning unused or under-used frequencies if the commitments are unfulfilled must be considered, as is the case with past spectrum assignment procedures.

ASSIGNMENT OPTIONS FOR NRAS

We can summarise NRAs' three basic options on assignment regimes as follows: In box A1 (Table 1) for instance, coverage obligations are defined ex-ante, with the primary focus of the assignment bid on the fee. For instance, in a recent decision, the Italian NRA, AGCom 32 ,required 5G frequency users to deploy BBD or UBB networks "in all provinces" within a pre-determined timeline of 24 months for the 3600-3800 MHz band, 36 months for the 700MHz band, and 48 months for the 26GHz band.

Assignment regime 1, Auction on Fees with Coverage Obligations, prioritizes fees over investment. Scenario 2, Negotiated Frequencies-for-Investments, presents competition issues for new frequency assignments and is better suited to licence renewal. Assignment regime 3, Auction on Investments, conforms to the spirit of the new EECC by prioritizing industry, social and economic objectives.

Public policy objectives can change over time, based on timely assessments of market situations, as illustrated by the French NRA, ARCEP example shown in Annex.

WHERE WE ARE AND FUTURE PERSPECTIVES

If we observe the details of spectrum assignment in the recent years in Europe, it appears that procedures have departed from simplistic Econ 101 models. All entities in charge have strived to adjust to network development imperatives. Member States have had different starting points, but convergence and consistency are essential for the EU's Digital Single Market, in terms of rules, timing, and conditions. The re-balanced spectrum 32 AGCom Delibera n. 231/18/CONS 74 Gliaggiudicatarideidirittid'usodellefrequenzenellebande700MHzSDL,3600-awards framework corresponds to an EU-wide perspective and can propose a certain number of good practices.

Further research will include analysis of practices outside the EU. There is a lot to be learnt through inter-region best practice sharing. Regulation principles across the Atlantic regarding network access, competition monitoring, have diverged now for 20 years, but from the American experience, for instance, incentive auctions could provide food for thought. China, meanwhile has focussed on administrative licensing. The general context, differences in political regimes, governance, and scale makes it nearly impossible to compare wireless developments with the EU, but the country's rapid progress on 5G demands attention. As for Japan, it has stuck to administrative management of spectrum and techno-administrative determination of spectrum fees. This situation is currently being debated in Japanese government circles and there have been constructive recent discussion between academics. Far-reaching cooperation developments with the EU could pave the way for more exchanges of experiences.

CONCLUSIONS: THE VALUE OF SPECTRUM RESIDES IN ITS USE BY THE ECONOMY AND SOCIETY

The purpose of this paper is to encourage a rethink of how spectrum assignment procedures can be organised to better balance the legitimate priority of raising revenues with the achievement of broader economic and social objectives. This requires the right incentives for operators to exploit the potential of future network technologies in fulfilling these objectives.

The author aimed to define a single optimum method for frequency assignment, with investment commitments by licence bidders as the overarching criterion. However, following an extensive two-year outreach and consultation programme with policy makers and regulators, including workshops in Brussels, Bonn, Rome, Madrid, Göteborg, London, Paris, Bangkok and Tokyo, we conclude that the most effective contribution at this stage is to highlight the policy choices facing governments, alongside the range of spectrum assignment designs that can be deployed to meet various public policy goals. Indeed, we hope to have made the case that once policy objectives have been prioritised, governments and regulators have at their disposal a full toolkit to adjust their spectrum assignment processes accordingly.

Our key message would be that it is time to put aside the fixation on auctions on fees as the panacea for competition and to focus instead on assignment processes. that underpin the competitive dynamic required to maximise and then realise the full potential of spectrum use to drive economic and social progress.

Priorities might vary between regions and over time, and spectrum assignment design will need to vary accordingly. Governments and NRAs can choose to exert discretionary powers to assess the priority objectives at each moment in time and define corresponding assignment designs. However, if financial considerations do take centre stage, it is important that governments consider the potential negative consequences both for the industry and the wider economy.

It is not too late to rethink spectrum awards for 5G from this perspective. Spectrum auctions 5.0 should put an end to the case by case game of successive spectrum assignments. It should pave the way for a consistent, less stochastic, system of putting spectrum at the service of society, and ensure openness to different use cases and adaptability to continuous technological evolution.

In achieving this it is important that governments and regulators continue to learn from each other and share best practice, both with the EU and beyond. The recently approved European Electronic Communications Code (EECC) formalises a process for voluntary peer review between Member States on spectrum assignment processes, overseen by the Radio Spectrum Policy Group (RSPG). This will provide an important vehicle for promoting better practice in spectrum assignment. We hope that this paper and our continued work in this area can contribute constructively to that process.

ANNEXES

DEPLOYMENT-INCENTIVE ASSIGNMENT PROCEDURE

SUMMARY SAMPLE APPLICATION FORM

This sample is for illustration purposes only. It is directly inspired by recent real-life procedures but adjusted to conform to the deployment incentive objectives we have set out in this paper.

1. Designation of frequencies relevant for the participation in the procedure for the granting of rights to use.

2. Possession of the requirements set out in the subsequent call for tenders for the general authorization. These may include, among other things, the technical and commercial suitability of the subject to use the frequencies in question and the provide related services.

3. Participation is guaranteed by a suitable security deposit fixed in the call for tenders. The security deposit can be adjusted to the progress of the competitive improvements, according to the call for tenders.

4. When submitting the application, and under penalty of exclusion, the participants explicitly accept the obligations deriving from the assignment of the frequencies subject of the present provision, in particular the assignment, where envisaged, in shared mode as specified in this provision, and that of the collective obligations referred to in art. X.

5. Those entitled to the use of the frequencies are identified, for each right of use, on the basis of rankings expressed by band and for the reserved lot, based on the objectives offered through a system of competitive improvements, according to the modalities established in the call for tenders, starting from a minimum level, established for each lot.

6. All the procedures referred to in this provision are carried out as part of a single allocation procedure.

7. The ranking lists awarded pursuant to this article are made public by the Administration. In the event of a tie between two or more bidder bids, the order is determined by drawing lots.

8. Successful tenderers are required to pay a frequency fee for the relative rights of use, as a contribution to the use of radio frequencies. Those are based on the predetermined amount, affected by a coefficient 0<X<1 corresponding to the investment effort. The pre-determined amount is defined by an international benchmark and an assessment of costs and profitability. Coefficient 0 corresponds to 100% deployment and results in no or minimal frequency fee. Coefficient 1, no coverage commitment results in full frequency fee" 9. The winning bidders are required to pay the frequency fee produced at the end of the procedures. The payment of the bidder awarded is paid in instalments according to the procedures laid down in the call for tenders.

SPECTRUM POLICY OBJECTIVES: SURVEYING NRAS' MISSION

STATEMENTS

Considering the push at European Union level in the last two decades towards market mechanisms as the right conceptual approach to the role and regulation of the telecommunications industry, one could think visions would have converged across countries in Europe. A quick survey of NRAs' public mission statements in seven EU countries shows there are nuances across countries that partly explain the difficulty in coming up with harmonised spectrum assignment procedures in the EU. 33

UK

The Digital Economy Act 2017 34 "…will:

o empower consumers and provide better connectivity so that everyone has access to broadband wherever they live o build a better infrastructure fit for the digital future o enable better public services using digital technologies o provide important protections for citizens from spam email and nuisance calls and protect children from online pornography"

To quote also from Ofcom 35 :

"We make sure that people in the UK get the best from their communications services and are protected from scams and sharp practices, while ensuring that competition can thrive. We operate under a number of Acts of Parliament, including in particular the Communications Act 2003. We must act within the powers and duties set for it by Parliament in legislation.

The Communications Act says that Ofcom's principal duty is to further the interests of citizens and of consumers, where appropriate by promoting competition. Meeting this duty is at the heart of everything we do.

… The UK NRA Ofcom's role includes securing

• the optimal use for wireless telegraphy of the electro-magnetic spectrum;

• that a wide range of electronic communications services is available throughout the UK; • that a wide range of TV and radio services of high quality and broad appeal are available throughout the UK; • that sufficient plurality in the providers of different television and radio services is maintained; • the application of standards that provide adequate protection for members of the public and others against offensive or harmful material in television and radio."

Ofcom's missions combine technical, social and economic considerations. It is to be noted "the interests of citizens and consumers" are to be furthered "where appropriate by promoting competition", which is a strongly limiting statement in the homeland of Manchester liberalism. This at least opens the door to qualified, not true market competition. Ofcom has demonstrated its ability to come up with innovative, broadminded policies with a sharp eye for economic and social impacts "throughout the UK".

FRANCE

The French NRA, ARCEP has recently (January 2018) published a new and updated Manifeste de l'ARCEP: "Les réseaux comme bien commun » (Networks as common goods), which decisively puts forward the "public nature" of exchange networks36 .

"The exchange networks, Internet, fixed, mobile telecom and postal, constitute an "infrastructure of freedoms". Freedom of expression and communications, freedom of access to knowledge and sharing, but also freedom of business and innovations, the key challenge for the competitiveness of the country, growth, and employment. Because the full exercise of these freedoms is essential in an open, innovative and democratic society, the national and European institutions make sure that the exchange networks develop like a "public good", whatever their mode of property, i.e. they express strong requirements in terms of accessibility universality, performance, neutrality, trust, and loyalty"

By outlining this "public nature" of networks, ARCEP provides a firm legal basis for extended requirements warranted from networks, both fixed and wireless.

GERMANY

Germany's BNetzA asserts its broadband policy objectives in reference to the Joint initiative by France, Germany, Italy and Spain, Europe's digital agenda presented at the EU Digital Summit in Talinn (September 201737 ):

"In parallel, we must act proactively in several areas that will allow our economies and societies to make full use of the potential benefits of digital technologies. We refer to five specific priorities for the next months and 2018. More specific award conditions and auction rules dealing with coverage obligations, service provider arrangements and licence duration will be put out for public consultation for an intended finalization by the end of 201838 .

ITALY

At the highest level AGCOM is defined by its competition monitoring activities, as well as its role concerning the protection of consumers and users: "Agcom is first and foremost a monitoring Authority: the law entrusts the Authority with the double task of ensuring a correct competition of operators on the market and of protecting consumers' fundamental freedoms"39 .

Concerning spectrum management, AGCOM refers to the budget law which includes measures in favour of mobile and wireless 5G systems40 .

SPAIN

Real Decreto41 concentrates on public and universal service provision and consumer protection. Regarding the telecommunications markets, strong emphasis is placed on competition.

SWEDEN

The Digital agenda for Sweden, published in 2011 42 , emphasizes the role of the digital industry as a main driver of economic development. The country consistently achieves above average mobile deployment in the EU 43 . This result has been reached through carefully designed and focused spectrum management methods. Maximizing the socioeconomic impact of radio spectrum usage comes first and foremost in spectrum management as exposed in the 2014 PTS Swedish Spectrum Strategy 44 . Eight principles are defined:

"To maximise the long-term societal benefit of radio spectrum in Sweden:

• Increase the availability of useful spectrum • Promote the sharing of all spectrum between different spectrum uses in the longterm • Enable a large diversity of spectrum uses to facilitate maximum societal benefit • Enable that all spectrum uses are placed in or migrated to the physically and socio-economically most suitable frequency bands over the long-term • Promote broad international harmonisation • A Societal cost-benefit analysis will form the basis for the choices that PTS makes in spectrum management

• A Societal cost-benefit analysis and needs assessment will guide spectrum allocation in comprehensive spectrum planning • For other spectrum uses, demand will as far as possible govern spectrum assignment "

Strong emphasis is placed on a societal cost-benefit analysis. Different regimes apply to public and commercial use of spectrum. Although it can be said that a literal reading of the framework presentation of the objectives of all EU 7 countries' NRAs showcases a nuanced picture, they essentially combine the same elements, albeit with nuanced emphasis. The mission statements for EU 7 NRAs relate to three different levels:

-High-level economic and social objectives are particularly strong in the mission statements from PTS, ARCEP, Ofcom, BNetzA, The Netherlands 45 https://www.government.nl/documents/reports/2017/03/07/radio-spectrum-policy-memorandum-2016

-Technical level network deployment objectives are present in all EU 7 NRAs, but appear as #1 for Italy at Government level -Competition control and enforcement are also current in all mission statements.

They appear as a #1 priority for Italy and Spain.

Mission statements by 7 EU NRAs draw a nuanced, but comprehensive vision, combining competition considerations and broader public policy objectives. Our intent here has been to illustrate the diversity of views which still exists among countries within the EU, not to conduct a comprehensive survey. Further research within and beyond Europe would certainly be useful as well, to better understand differences and possibly bring closer policies and regulations.

Social and economic impacts, whatever the efforts recently devoted to analysing them, can be conceptually and practically hard to precisely measure and quantify 46 . If all the growth percentage points supposed to derive in the last three decades from computers, networks, all digital whatnots, were summed up, our economies would fly at space shuttle speeds. What is easier however to quantify is the objectives, the coverage and deployment schedule which are explicitly defined in the assignment procedure. It is to be noted the definition of the goals leaves ample room for debate: universal coverage and deployment, for instance, is not a recognised universal truth.

DEFINING PRIORITY OBJECTIVES AND CORRESPONDING PROCEDURES OVER TIME

Public policy objectives can change over time, based on timely assessments of market situations. The French NRA, ARCEP, has developed an interesting tabular overview of the objectives successively pursued during generations of spectrum awards. These include:

-Monetizing state's intangible assets, with auctions as a preferred tool; -Digital development, with coverage as the central criterion; -Competition issues, with introduction of a 4 th entrant, then provision for MVNOs, set aside mechanisms and spectrum caps; -Innovation, with minimum data rate; -Other objectives.

  ON FREQUENCY FEES WITH IMPROVED COVERAGE

TABLE 1

 1

	Assignment regime	1	2	3
		Auction on Fees with	Negotiated	Auction on
	Criteria	Coverage Obligations	Frequencies-for-	Investments
			Investments
	A. Network deployment	NRA discretion on	Trade-off between	NRA
	coverage	coverage: potentially	NRA and bidders	requirements
		high or close to 100%		Bidders' business
				considerations
	B. Competitiveness	Distorted by focus on	Limited	High
		fees		focus on policy
		Oligopoly limitations		objectives
	C. Frequency fee	Highly	Presumably low in the	To be determined
		detrimental to	short-term	Endogenous or
		investments		exogenous

  6.2.7 THE NETHERLANDSTo quote from the 2016 Radio Spectrum Policy Memorandum 45 : "The government's duty is to allocate the radio spectrum in such a way that it is of overall benefit to the economic, social and cultural interests that are attached to frequency use. The central objective of effective frequency use continues to be upheld in the radio spectrum policy, however, a shift in focus is needed. Where the Radio Spectrum Policy Memorandum 2005 primarily focused on the economic interest, a change in focus takes place that is aimed at the ever increasing societal dependence and public interest.The fundamental principle of the radio spectrum policy remains a market that operates efficiently, whilst safeguarding public-interest tasks. In the first instance, this is achieved by awarding (scarce) licenses. Limited spectrum licenses continue to be awarded principally through auctions, with extensions granted where social reasons necessitate them. In this context, it is essential to shape the market in such a way that it is capable of responding to social developments to the fullest extent possible."This document signals an awareness of the shift to a new paradigm in spectrum policies and assignment methods.6.2.8 CONCLUSION: EU 7 NRA MISSION STATEMENTS

We focus on mobile wireless and leave aside at this stage the equally critical and closely linked domain of broadcasting.

Noah Smith, Most of What You Learned in Econ 101 Is Wrong, The theory is out of date, 24 November 2015, https://www.bloomberg.com/view/articles/2015-11-24/most-of-what-you-learned-in-econ-101-iswrong

The frequent use of the term "market failure" in the telecommunications networks context is questionable. Achieving 100% penetration cannot be the universally expected outcome in all markets. "Limited market penetration" would be more appropriate.

Ibid. Noah Smith, Most of What You Learned in Econ 101 Is Wrong, The theory is out of date, 24 November 2015, https://www.bloomberg.com/view/articles/2015-11-24/most-of-what-you-learned-inecon-101-is-wrong

 6 Roger E. Backhouse, Béatrice Cherrier, The Age of the Applied Economist: The Transformation of Economics since the 1970s, History of Political Economy (Dec 2017) 49 (Supplement): 1-33. https://doi.org/10.1215/00182702-4166239, Available at SSRN: https://ssrn.com/abstract=2868144 or http://dx.doi.org/10.2139/ssrn.2868144

GSMA, Effective spectrum pricing helps boost mobile services, 22 February, 2017, https://www.gsma.com/spectrum/effective-spectrum-pricing/

NERA Economics for GSMA, Effective Spectrum Pricing, , 2007, P31, http://www.gsma.com/spectrum/effective-spectrum-pricing/

European Commission, Study on spectrum assignment in the European Union, 4 October 2017, https://publications.europa.eu/en/publication-detail/-/publication/2388b227-a978-11e7-837e-01aa75ed71a1/language-en

 13 European Commission, Study on Spectrum Assignment in the European Union, 2017,

p100 14 Carlo Cambini, Nicola Garelli, Spectrum fees and market performance: A quantitative analysis, Telecommunications Policy, Volume 41, Issues 5-6, June 2017, pp 355-366

Thomas W. Hazlett, Roberto E. Muñoz, What Really Matters in Spectrum Allocation Design, 2012, p102

Gerard Pogorel & Erik Bohlin (2017), Spectrum 5.0: Improving assignment procedures to meet economic and social policy goals, A position paper, Working paper; https://www.researchgate.net/publication/316524026_Spectrum_50_Improving_assignment_procedures_t o_meet_economic_and_social_policy_goals_A_position_paper

Commission Impact Assessment Guidelines (January 2009) -Pogorel et al., ITU Spectrum Management Training Program, Socio-Economic Impact of Spectrum Regulation: Competition and Consumer Protection, 2015

Digital Europe, 5G Policy Recommendations, January 2018, p.1. http://www.digitaleurope.org/DesktopModules/Bring2mind/DMX/Download.aspx?Command=Core_Do wnload&EntryId=2595&language=en-US&PortalId=0&TabId=353

Francois Jeanjean, Julienne Liang, Mobile investment per capita tends to increase with license duration, February

20, 2018, Working Paper, https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3184200 20 https://www.agcom.it/documents/10179/3478659/Allegato+7-8-2018/637af9a9-8a60-4b3e-8ac0-3ce2cd808ac4?version=1.0

ARCEP, https://www.arcep.fr/actualites/les-communiques-de-presse/detail/n/new-deal-mobile-1.html, 2 August 2018

PolicyTracker, https://www.policytracker.com/colombia-may-abolish-maximised-spectrum-prices

ARCEP, https://www.arcep.fr/actualites/les-communiques-de-presse/detail/n/new-deal-mobile-1.html

PTS (2011). Open invitation to apply for a license to use radio transmitters in the 800 MHz band. https://www.pts.se/upload/Beslut/Radio/2010/10-10534-open-invitation-800-mhz-auction-dec10.pdf

https://ens.dk/ansvarsomraader/frekvenser/auktioner-og-udbud-frekvenser

For example, obligations would be contingent on government and local authorities abiding by the Broadband Cost Reduction Directive

https://www.arcep.fr/uploads/tx_gspublication/manifesto-arcep-eng-2018.pdf

https://ec.europa.eu/commission/publications/tallinn-digital-summit-factsheets_en Joint initiative by France, Germany, Italy and Spain, Europe's digital agenda: Deliverables for the Digital Summit in Tallinn, page 2; September 2017; www.bundesregierung.de

Process for the award of 5G spectrum; BK1-17/001 https://www.bundesnetzagentur.de/SharedDocs/Downloads/EN/Areas/Telecommunications/Companies/T elecomRegulation/FrequencyManagement/ElectronicCommunicationsServices/FrequencyAward2018/20 180514_Information_DecisionI&II.pdf?__blob=publicationFile&v=2

https://www.agcom.it/che-cos-e-l-autorita

Delibera n. 231/18/CONS p. 5

Real Decreto

424/2005, de 15 de abril, por el que se aprueba el Reglamento sobre las condiciones para la prestación de servicios de comunicaciones electrónicas, el servicio universal y la protección de los usuarios.

-Commission Impact Assessment Guidelines (January 2009) -Pogorel et al. (2015), ITU Spectrum Management Training Program "Socio-Economic Impact of Spectrum Regulation: Competition and Consumer Protection"

octobre

FromARCEP, 2018, unpublished This analysis shows that:-Award criteria vary over time depending on the perception of the market and the policy priorities set by the Government and the NRA -Auctions can be combined with other policy tools.

research was supported by Ericsson. It has benefitted from previous work supported by AGCom, ANFr, BNetzA, CEPS, the European Commission, Qualcomm Inc., and the ITU.


Jocelyne Erhel

Nuentsa Wakam

About Parallel Variants of GMRES Algorithm

Solving large sparse linear systems is at the heart of many numerical simulations Simulation of the velocity field on the Greenland inlandsis, with Elmer/Ice model Image :

practical issues

Arnoldi process 1: v 1 = r 0 / r 0 2 2: for k = 1, m do 3:

p = Bv k

4:

for i = 1 : k do 5:

h ik = v T i p 6: p = p -h ik v i 7:
end for 8: Generate the basis vectors [Reichel 1990, Bai et al 1994] Orthogonalize the basis [JE 1995, Sidje 1997, Demmel et al 2011] Compute the basis block by block [De Sturler 1994, Hoemmen 2010] Preconditioning issues

⇒

GMRES ... practical issues

Arnoldi process 1:

v 1 = r 0 / r 0 2 2: for k = 1, m do 3: p = Bv k

4:

for i = 1 : k do 5:

h ik = v T i p 6: p = p -h ik v i 7:
end for 8:

h k+1,k = ||p|| 2 9: v k+1 = p/h k+1,k 10: end for ⇓ BVm = V m+1 Hm
Granularity issues in parallel algorithms ⇒ Communication-avoiding strategies Generate the basis vectors [Reichel 1990, Bai et al 1994] Orthogonalize the basis [JE 1995, Sidje 1997, Demmel et al 2011] Compute the basis block by block [De Sturler 1994, Hoemmen 2010] Preconditioning issues

⇒

GMRES ... practical issues

Arnoldi process 1:

v 1 = r 0 / r 0 2 2: for k = 1, m do 3: p = Bv k

4:

for i = 1 : k do 5:

h ik = v T i p 6: p = p -h ik v i 7:
end for 8:

h k+1,k = ||p|| 2 9: v k+1 = p/h k+1,k 10: end for ⇓ BVm = V m+1 Hm
Granularity issues in parallel algorithms ⇒ Communication-avoiding strategies Generate the basis vectors [Reichel 1990, Bai et al 1994] Orthogonalize the basis [JE 1995, Sidje 1997, Demmel et al 2011] Compute the basis block by block [De Sturler 1994, Hoemmen 2010] Preconditioning issues

⇒

practical issues

Arnoldi process 1: v 1 = r 0 / r 0 2 2: for k = 1, m do 3:

p = Bv k

4:

for i = 1 : k do 5:

h ik = v T i p 6: p = p -h ik v i 7:
end for 8:

h k+1,k = ||p|| 2 9: v k+1 = p/h k+1

4:

for i = 1 : k do 5:

h ik = v T i p 6: p = p -h ik v i 7:
end for 8:

M -1 RAS = D k=1 (R 0 k ) T (A δ k ) -1 R δ k
Setup the submatrices (ILU or LU factorization).

Solve iteratively the preconditioned system using GMRES. Variable block size s j and Krylov size l 1 = s 1 , l j = l j-1 + s j , j ≥ 2 [Imberti and JE 2017] Build a basis W l j of the Krylov subspace K l j for 1 ≤ j ≤ J Build an orthonormal basis V l j +1 of the Krylov subspace K l j +1 get the Arnoldi-like relation BW l j = V l j +1 H l j

Minimize the residual in the Krylov subspace x = x 0 + M -1 W l j y implies r = r 0 -BW l j y = V l j +1 (βe 1 -H l j y )

Solve the least-squares problem: min

y ∈R l j βe 1 -H l j y
Test convergence at each step j

Restart if not converged at step J with l J = m Build a basis W l j of the Krylov subspace K l j for 1 ≤ j ≤ J Build an orthonormal basis V l j +1 of the Krylov subspace K l j +1 get the Arnoldi-like relation BW l j = V l j +1 H l j

x 0 = x 0 + M -1 Wmym
Minimize the residual in the Krylov subspace x = x 0 + M -1 W l j y implies r = r 0 -BW l j y = V l j +1 (βe 1 -H l j y )

Solve the least-squares problem: min

y ∈R l j βe 1 -H l j y
Test convergence at each step j

Restart if not converged at step J with l J = m Build a basis W l j of the Krylov subspace K l j for 1 ≤ j ≤ J Build an orthonormal basis V l j +1 of the Krylov subspace K l j +1 get the Arnoldi-like relation BW l j = V l j +1 H l j

x 0 = x 0 + M -1 Wmym
Minimize the residual in the Krylov subspace x = x 0 + M -1 W l j y implies r = r 0 -BW l j y = V l j +1 (βe 1 -H l j y )

Solve the least-squares problem: min

y ∈R l j βe 1 -H l j y
Test convergence at each step j

Restart if not converged at step J with l J = m Build a basis W l j of the Krylov subspace K l j for 1 ≤ j ≤ J Build an orthonormal basis V l j +1 of the Krylov subspace K l j +1 get the Arnoldi-like relation BW l j = V l j +1 H l j

x 0 = x 0 + M -1 Wmym
Minimize the residual in the Krylov subspace x = x 0 + M -1 W l j y implies r = r 0 -BW l j y = V l j +1 (βe 1 -H l j y )

Solve the least-squares problem: min

y ∈R l j βe 1 -H l j y
Test convergence at each step j

Restart if not converged at step J with l J = m Build a basis W l j of the Krylov subspace K l j for 1 ≤ j ≤ J Build an orthonormal basis V l j +1 of the Krylov subspace K l j +1 get the Arnoldi-like relation BW l j = V l j +1 H l j

x 0 = x 0 + M -1 Wmym
Minimize the residual in the Krylov subspace x = x 0 + M -1 W l j y implies r = r 0 -BW l j y = V l j +1 (βe 1 -H l j y )

Solve the least-squares problem: min

y ∈R l j βe 1 -H l j y
Test convergence at each step j

Restart if not converged at step J with l J = m

x 0 = x 0 + M -1 Wmym FibGMRES DI & JE &DNW GMRES DGMRES
and AGMRES

VGMRES

Block computation and orthogonalization with VGMRES(m,s)

Step j of VGMRES(m,s)

Initialization: r 0 = b -Ax 0 , β = r 0 , v 1 = r 0 /β, W 0 = ∅, V 1 = [v 1 ]
Block j of size s j , with 1 ≤ j ≤ J with an adaptive choice of s j such that s j ≤ s First step: s j matrix vector products Compute the block C j as a basis of Ks j (B, u) with u = v l j-1 +1

Compute the block BC j

Parallel preconditioning t = M -1 u then parallel matrix-vector product At Define the Krylov basis by

W l j = W l j-1 , C j
Second step: orthogonalization 1997, JE 1995] ] or TSQR [Demmel et al 2011] By induction, get the Arnoldi-like relation

BC j = V l j +1 S j RODDEC [Sidje
v 1 , BW l j = V l j +1 R l j +1 , BW l j = V l j +1 H l j

VGMRES

Block computation and orthogonalization with VGMRES(m,s)

Step j of VGMRES(m,s)

Initialization: r 0 = b -Ax 0 , β = r 0 , v 1 = r 0 /β, W 0 = ∅, V 1 = [v 1 ]
Block j of size s j , with 1 ≤ j ≤ J with an adaptive choice of s j such that s j ≤ s First step: s j matrix vector products Compute the block C j as a basis of Ks j (B, u) with u = v l j-1 +1

Compute the block BC j

Parallel preconditioning t = M -1 u then parallel matrix-vector product At Define the Krylov basis by

W l j = W l j-1 , C j
Second step: orthogonalization 1997, JE 1995] ] or TSQR [Demmel et al 2011] By induction, get the Arnoldi-like relation

BC j = V l j +1 S j RODDEC [Sidje
v 1 , BW l j = V l j +1 R l j +1 , BW l j = V l j +1 H l j

VGMRES

Block computation and orthogonalization with VGMRES(m,s)

Step j of VGMRES(m,s)

Initialization: r 0 = b -Ax 0 , β = r 0 , v 1 = r 0 /β, W 0 = ∅, V 1 = [v 1 ]
Block j of size s j , with 1 ≤ j ≤ J with an adaptive choice of s j such that s j ≤ s First step: s j matrix vector products Compute the block C j as a basis of Ks j (B, u) with u = v l j-1 +1

Compute the block BC j

Parallel preconditioning t = M -1 u then parallel matrix-vector product At Define the Krylov basis by

W l j = W l j-1 , C j
Second step: orthogonalization 1997, JE 1995] ] or TSQR [Demmel et al 2011] By induction, get the Arnoldi-like relation

BC j = V l j +1 S j RODDEC [Sidje
v 1 , BW l j = V l j +1 R l j +1 , BW l j = V l j +1 H l j

VGMRES

Block computation and orthogonalization with VGMRES(m,s)

Step j of VGMRES(m,s)

Initialization: r 0 = b -Ax 0 , β = r 0 , v 1 = r 0 /β, W 0 = ∅, V 1 = [v 1 ]
Block j of size s j , with 1 ≤ j ≤ J with an adaptive choice of s j such that s j ≤ s First step: s j matrix vector products Compute the block C j as a basis of Ks j (B, u) with u = v l j-1 +1

Compute the block BC j

Parallel preconditioning t = M -1 u then parallel matrix-vector product At Define the Krylov basis by

W l j = W l j-1 , C j
Second step: orthogonalization 1997, JE 1995] ] or TSQR [Demmel et al 2011] By induction, get the Arnoldi-like relation

BC j = V l j +1 S j RODDEC [Sidje
v 1 , BW l j = V l j +1 R l j +1 , BW l j = V l j +1 H l j

VGMRES

Communication issues

The number of messages is related to the number of steps J Objective: reduce the number of steps

VGMRES

Communication issues

The number of messages is related to the number of steps J Objective: reduce the number of steps

FibGMRES

  = b, A ∈ R n×n x, b ∈ R n B = AM -1 x 0 ∈ R n r 0 = b -Ax 0GMRES(m): a Krylov subspace method[Saad and Schultz 1986, Meurant's book 1999, Saad's book 2003, Simoncini and Szyld 2007, JE 2011, ...]Km(B, r 0 ) = span{r 0 , Br 0 , . . . B m-1 r 0 } Find xm ∈ x 0 + M -1 Km(B, r 0 ) such that rm 2 = b -Bxm 2 = min x∈x 0 +M -1 Km (B,r 0 ) b -Bx 2Building blocks of GMRES(m)Build an orthonormal basis V k+1 of the Krylov subspace K k+1 get the Arnoldi-like relationBV k = V k+1 H k for k = 1, . . . , mMinimize the residual in the Krylov subspacex = x 0 + M -1 V k y implies r = r 0 -BV k y = V k+1 (βe 1 -H k y ) Solve the least-squares problem: min y ∈R k βe 1 -= b, A ∈ R n×n x, b ∈ R n B = AM -1 x 0 ∈ R n r 0 = b -Ax 0 GMRES(m): a Krylov subspace method [Saadand Schultz 1986, Meurant's book 1999, Saad's book 2003, Simoncini and Szyld 2007, JE 2011, ...]Km(B, r 0 ) = span{r 0 , Br 0 , . . . B m-1 r 0 } Find xm ∈ x 0 + M -1 Km(B, r 0 ) such that rm 2 = b -Bxm 2 = min x∈x 0 +M -1 Km (B,r 0 ) b -Bx 2Building blocks of GMRES(m)Build an orthonormal basis V k+1 of the Krylov subspace K k+1 get the Arnoldi-like relationBV k = V k+1 H k for k = 1, . . . , mMinimize the residual in the Krylov subspace x = x 0 + M -1 V k y implies r = r 0 -BV k y = V k+1 (βe 1 -H k y ) Solve the least-squares problem: min y ∈R k βe 1 -

  multilevel methods to deal with large systems Schwarz preconditioning [Atenekeng Kahou et al 2007, Dufaud+Tromeur-Dervout 2010, Giraud+Haidar 2009,..] Filtering and Schur complement [Li et al 2003, Grigori et al 2011] Multilevel parallelism [Nuentsa Wakam et al 2011, Giraud et al 2010, ...] Complexity and stagnation issues with restarted GMRES(m) ⇒ deflation to recover possible loss of information Deflation by preconditioning [JE et al 1996, Burrage et al 1998, Baglama et al 1998, ...] Deflation by augmented basis [Morgan 1995, Morgan 2002,...] Strategy Combine 'communication-avoiding' GMRES ... and Deflation ... and Domain Decomposition preconditioners [Nuentsa Wakam et al 2013, Nuentsa Wakam and Pacull 2013, Nuentsa Wakam and JE 2013]

FibGMRES

  multilevel methods to deal with large systems Schwarz preconditioning [Atenekeng Kahou et al 2007, Dufaud+Tromeur-Dervout 2010, Giraud+Haidar 2009,..] Filtering and Schur complement [Li et al 2003, Grigori et al 2011] Multilevel parallelism [Nuentsa Wakam et al 2011, Giraud et al 2010, ...] Complexity and stagnation issues with restarted GMRES(m) ⇒ deflation to recover possible loss of information Deflation by preconditioning [JE et al 1996, Burrage et al 1998, Baglama et al 1998, ...] Deflation by augmented basis [Morgan 1995, Morgan 2002,...] Strategy Combine 'communication-avoiding' GMRES ... and Deflation ... and Domain Decomposition preconditioners [Nuentsa Wakam et al 2013, Nuentsa Wakam and Pacull 2013, Nuentsa Wakam and JE 2013]

FibGMRES

  multilevel methods to deal with large systems Schwarz preconditioning [Atenekeng Kahou et al 2007, Dufaud+Tromeur-Dervout 2010, Giraud+Haidar 2009,..] Filtering and Schur complement [Li et al 2003, Grigori et al 2011] Multilevel parallelism [Nuentsa Wakam et al 2011, Giraud et al 2010, ...] Complexity and stagnation issues with restarted GMRES(m) ⇒ deflation to recover possible loss of information Deflation by preconditioning [JE et al 1996, Burrage et al 1998, Baglama et al 1998, ...] Deflation by augmented basis [Morgan 1995, Morgan 2002,...] Strategy Combine 'communication-avoiding' GMRES ... and Deflation ... and Domain Decomposition preconditioners [Nuentsa Wakam et al 2013, Nuentsa Wakam and Pacull 2013, Nuentsa Wakam and JE 2013]

FibGMRES

  vectors[Reichel 1990, Bai et al 1994] Orthogonalize the basis[JE 1995, Sidje 1997, Demmel et al 2011] Compute the basis block by block[De Sturler 1994, Hoemmen 2010] Preconditioning issues ⇒ multilevel methods to deal with large systems Schwarz preconditioning [Atenekeng Kahou et al 2007, Dufaud+Tromeur-Dervout 2010, Giraud+Haidar 2009,..] Filtering and Schur complement [Li et al 2003, Grigori et al 2011] Multilevel parallelism [Nuentsa Wakam et al 2011, Giraud et al 2010, ...] Complexity and stagnation issues with restarted GMRES(m) ⇒ deflation to recover possible loss of information Deflation by preconditioning [JE et al 1996, Burrage et al 1998, Baglama et al 1998, ...] Deflation by augmented basis [Morgan 1995, Morgan 2002,...] Strategy Combine 'communication-avoiding' GMRES ... and Deflation ... and Domain Decomposition preconditioners [Nuentsa Wakam et al 2013, Nuentsa Wakam and Pacull 2013, Nuentsa Wakam and JE 2013]

FibGMRES

  Building blocks of m-step GMRES(m) Build a basis W m+1 of the Krylov subspace K m+1 such that BWm = W m+1 T m+1Build an orthonormal basis V m+1 of K m+1 such that W m+1 = V m+1 R m+1 get the Arnoldi-like relations BWm = V m+1 Hm and BVm = V m+1 HmR -1 m[Nuentsa Wakam and JE 2013, Hoemmen 2010] Minimize the residual in the Krylov subspace x = x 0 + M -1 Vmy implies r = r 0 -BVmy = V m+1 (βe 1 -HmR -Alternative to minimize the residual in the Krylov subspace [Imberti and JE 2017] x = x 0 + M -1 Wmy implies r = r 0 -BWmy = V m+1 (βe 1 -Hmy ) Solve the least-squares problem: min Building blocks of m-step GMRES(m) Build a basis W m+1 of the Krylov subspace K m+1 such that BWm = W m+1 T m+1 Build an orthonormal basis V m+1 of K m+1 such that W m+1 = V m+1 R m+1 get the Arnoldi-like relations BWm = V m+1 Hm and BVm = V m+1 HmR -1 m [Nuentsa Wakam and JE 2013, Hoemmen 2010] Minimize the residual in the Krylov subspace x = x 0 + M -1 Vmy implies r = r 0 -BVmy = V m+1 (βe 1 -HmR -Alternative to minimize the residual in the Krylov subspace [Imberti and JE 2017] x = x 0 + M -1 Wmy implies r = r 0 -BWmy = V m+1 (βe 1 -Hmy ) Solve the least-squares problem: min Building blocks of m-step GMRES(m) Build a basis W m+1 of the Krylov subspace K m+1 such that BWm = W m+1 T m+1 Build an orthonormal basis V m+1 of K m+1 such that W m+1 = V m+1 R m+1 get the Arnoldi-like relations BWm = V m+1 Hm and BVm = V m+1 HmR -1 m [Nuentsa Wakam and JE 2013, Hoemmen 2010] Minimize the residual in the Krylov subspace x = x 0 + M -1 Vmy implies r = r 0 -BVmy = V m+1 (βe 1 -HmR -1 m y ) Solve the least-squares problem: min Alternative to minimize the residual in the Krylov subspace [Imberti and JE 2017] x = x 0 + M -1 Wmy implies r = r 0 -BWmy = V m+1 (βe 1 -Hmy ) Solve the least-squares problem: min GMRES(m) Building blocks of m-step GMRES(m) Build a basis W m+1 of the Krylov subspace K m+1 such that BWm = W m+1 T m+1 Build an orthonormal basis V m+1 of K m+1 such that W m+1 = V m+1 R m+1 get the Arnoldi-like relations BWm = V m+1 Hm and BVm = V m+1 HmR -1 m [Nuentsa Wakam and JE 2013, Hoemmen 2010] Minimize the residual in the Krylov subspace x = x 0 + M -1 Vmy implies r = r 0 -BVmy = V m+1 (βe 1 -HmR -1 m y ) Solve the least-squares problem: min Alternative to minimize the residual in the Krylov subspace [Imberti and JE 2017] x = x 0 + M -1 Wmy implies r = r 0 -BWmy = V m+1 (βe 1 -Hmy ) Solve the least-squares problem: min GMRES(m) Building blocks of m-step GMRES(m) Build a basis W m+1 of the Krylov subspace K m+1 such that BWm = W m+1 T m+1 Build an orthonormal basis V m+1 of K m+1 such that W m+1 = V m+1 R m+1 get the Arnoldi-like relations BWm = V m+1 Hm and BVm = V m+1 HmR -1 m [Nuentsa Wakam and JE 2013, Hoemmen 2010] Minimize the residual in the Krylov subspace x = x 0 + M -1 Vmy implies r = r 0 -BVmy = V m+1 (βe 1 -HmR -1 m y ) Solve the least-squares problem: min Alternative to minimize the residual in the Krylov subspace [Imberti and JE 2017] x = x 0 + M -1 Wmy implies r = r 0 -BWmy = V m+1 (βe 1 -Hmy ) Solve the least-squares problem: min GMRES(m) Building blocks of m-step GMRES(m) Build a basis W m+1 of the Krylov subspace K m+1 such that BWm = W m+1 T m+1 Build an orthonormal basis V m+1 of K m+1 such that W m+1 = V m+1 R m+1 get the Arnoldi-like relations BWm = V m+1 Hm and BVm = V m+1 HmR -1 m [Nuentsa Wakam and JE 2013, Hoemmen 2010] Minimize the residual in the Krylov subspace x = x 0 + M -1 Vmy implies r = r 0 -BVmy = V m+1 (βe 1 -HmR -1 m y ) Solve the least-squares problem: min Alternative to minimize the residual in the Krylov subspace [Imberti and JE 2017] x = x 0 + M -1 Wmy implies r = r 0 -BWmy = V m+1 (βe 1 -Hmy ) Solve the least-squares problem: min Computation of vectors w k Monomial basis: w k+1 = Bw k Newton basis: σ k+1 w k+1 = (B -α k+1 I )w k where the shifts α k are computed during a preliminary cycle of GMRES(m) and scaling is done with σ k [Reichel 1990, Bai et al 1994, JE 1995, Nuentsa Wakam and JE 2013] Chebyshev basis [Joubert+Carey 1992, Philippe+Reichel 2012] Stability and parallelism issues the condition number of Wm increases with m Parallel performances increases with m Main steps with Domain Decomposition preconditioning Partition the weighted graph of the matrix in parallel with PARMETIS.Redistribute the matrix and right-hand-side according to the PARMETIS partitioning.Perform a parallel iterative row and column scaling on the matrix and the right-hand side vector[Amestoy et al 2008].Define the overlap between the submatrices for the additive Schwarz preconditioner[Cai and Sarkis 1999, Efstathiou and Gander 2003]

FibGMRESFibGMRESFibGMRES

  depends on the spectral distribution in B Smallest eigenvalues slow down the convergence Deflation occurs when the Krylov subspace is large enough With restarting : loss of spectral information, risk of stalling Accelerating the restarted GMRES [Simoncini and Szyld, 2007] Approximate the smallest eigenvalues and the associated invariant subspace Ur Explicit deflation technique [JE et al 1996; Burrage et al 1998; Moriya et al 2000, Nuentsa Wakam et al 2013 ]: B M-1 x = b with M-1 = (In + Ur (|λn|T -1 -Ir )U T r and T = U T r BUr Augmented techniques [Morgan 2000, 2002, Giraud et al 2010, Nuentsa Wakam and JE 2013] xm ∈ x 0 + Km(B, r 0 )+span{Ur } depends on the spectral distribution in B Smallest eigenvalues slow down the convergence Deflation occurs when the Krylov subspace is large enough With restarting : loss of spectral information, risk of stalling Accelerating the restarted GMRES [Simoncini and Szyld, 2007] Approximate the smallest eigenvalues and the associated invariant subspace Ur Explicit deflation technique [JE et al 1996; Burrage et al 1998; Moriya et al 2000, Nuentsa Wakam et al 2013 ]: B M-1 x = bwith M-1 = (In + Ur (|λn|T -1 -Ir )U T r and T = U T r BUr Augmented techniques[Morgan 2000, 2002, Giraud et al 2010, Nuentsa Wakam and JE 2013] xm ∈ x 0 + Km(B, r 0 )+span{Ur }

FibGMRES

  preconditioned and deflated GMRES Variable s-step algorithm VGMRES(m,s) step VGMRES(m,s) Variable s step GMRES: VGMRES(m,s)

FibGMRES

  stepVGMRES(m,s) Variable s step GMRES: VGMRES(m,s) Variable block size s j and Krylov size l 1 = s 1 , l j = l j-1 + s j , j ≥ 2[Imberti and JE 2017]

FibGMRES

  stepVGMRES(m,s) Variable s step GMRES: VGMRES(m,s) Variable block size s j and Krylov size l 1 = s 1 , l j = l j-1 + s j , j ≥ 2[Imberti and JE 2017]

FibGMRES

  stepVGMRES(m,s) Variable s step GMRES: VGMRES(m,s) Variable block size s j and Krylov size l 1 = s 1 , l j = l j-1 + s j , j ≥ 2[Imberti and JE 2017]

FibGMRES

  stepVGMRES(m,s) Variable s step GMRES: VGMRES(m,s) Variable block size s j and Krylov size l 1 = s 1 , l j = l j-1 + s j , j ≥ 2[Imberti and JE 2017]

FibGMRES

FibGMRES

FibGMRES

FibGMRES

  k ) symmetric case: exponential growth of the condition number of a Krylov basis [Beckermann 2000] nonsymmetric case with |λ 1 | > |λ 2 | monomial basis C j = {u, Bu, . . . , B s j -1 u} [Imberti and JE 2017]κ(BC j ) ≥ cste |λ 1 /λ 2 | s j -1Choice of the block size s jObjective: small condition numbers of the first blocks fixed sequence s j = s: SGMRES(m,s) [Hoemmen 2010, ...] adaptive increasing sequence s j with s j ≤ s: VGMRES(m,s)[Imberti and JE 2017]

FibGMRES

  k ) symmetric case: exponential growth of the condition number of a Krylov basis [Beckermann 2000] nonsymmetric case with |λ 1 | > |λ 2 | monomial basis C j = {u, Bu, . . . , B s j -1 u} [Imberti and JE 2017]κ(BC j ) ≥ cste |λ 1 /λ 2 | s j -1Choice of the block size s jObjective: small condition numbers of the first blocks fixed sequence s j = s: SGMRES(m,s) [Hoemmen 2010, ...] adaptive increasing sequence s j with s j ≤ s: VGMRES(m,s)[Imberti and JE 2017]

FibGMRES

  Number of steps SGMRES(m,s): J = m/s steps VGMRES(m,s): J steps with l J = m and J = J 1 + J 2 FibGMRES(m,s): Fibonacci sequence capped at s J 2 = O(m/s), J 1 = O(log φ (s

  Number of steps SGMRES(m,s): J = m/s steps VGMRES(m,s): J steps with l J = m and J = J 1 + J 2 FibGMRES(m,s): Fibonacci sequence capped at s J 2 = O(m/s), J 1 = O(log φ (s

FibGMRESFibGMRES

  a small nonsymmetric matrix Nonsymmetric matrix CAGE10 of size n = 11397 and nonzeros nz = 150645 Convergence curves with m = 48 and s = 16 a small nonsymmetric matrix Nonsymmetric matrix CAGE10 of size n = 11397 and nonzeros nz = 150645 Condition numbers of AW with m = 48 and s = 16

FibGMRESFibGMRES

  a large nonsymmetric matrix Nonsymmetric matrix (PR02R + 1000 I) with n = 161070 and nz = 8185136 Condition numbers of AW with m = 96 and s = 16 or s = 32 a large restarting parameter Nonsymmetric matrix (PR02R + 1000 I) with n = 161070 and nz = 8185136 Convergence curves with m = 192 and s = 16 or s = 32 a large restarting parameter Nonsymmetric matrix (PR02R + 1000 I) with n = 161070 and nz = 8185136 Condition numbers of AW with m = 192 and s = 16 or s = 32 r) and AGMRES(m,r) Combined DD preconditioning with m-step GMRES and deflation Parallel efficiency and fast convergence with a large number of subdomains Difficult choice of the restarting parameter m VGMRES(m,s) and FibGMRES(m,s) s-step algorithm with a variable block size s j Relationship between convergence rate and condition numbers of the blocks Numerical experiments with a Fibonacci sequence Future work Adaptive variation of s Blocks computed via a Newton basis Combined DD preconditioning with variable s-step GMRES and deflation Parallel computations

FibGMRES

  r) and AGMRES(m,r) Combined DD preconditioning with m-step GMRES and deflation Parallel efficiency and fast convergence with a large number of subdomains Difficult choice of the restarting parameter m VGMRES(m,s) and FibGMRES(m,s) s-step algorithm with a variable block size s j Relationship between convergence rate and condition numbers of the blocks Numerical experiments with a Fibonacci sequence Future work Adaptive variation of s Blocks computed via a Newton basis Combined DD preconditioning with variable s-step GMRES and deflation Parallel computations r) and AGMRES(m,r) Combined DD preconditioning with m-step GMRES and deflation Parallel efficiency and fast convergence with a large number of subdomains Difficult choice of the restarting parameter m VGMRES(m,s) and FibGMRES(m,s) s-step algorithm with a variable block size s j Relationship between convergence rate and condition numbers of the blocks Numerical experiments with a Fibonacci sequence Future work Adaptive variation of s Blocks computed via a Newton basis Combined DD preconditioning with variable s-step GMRES and deflation Parallel computations