Variationnal Data assimilation, Earth, Atmosphere, Ocean · Introduction to data assimilation Dual...

Variationnal Data assimilation, Earth, Atmosphere,Ocean

Serge GrattonUniversity of Toulouse

CERFACS-IRIT, Toulouse, France

Joint work with S. Gurol, P. Jiranek, D. Titley-Peloquin, Ph.L. Toint, J. Tshimanga(CERFACS-IRIT)

O. Titaud, I. Mirouze, A. Weaver (CERFACS)L. Berre, G. Desroziers, H. Varella (Meteo-France)

R. Biancale, L. Seoane, W. Zerhouni (CNES)

ADTAO seminar, Toulouse 2013

Serge G. (CERFACS) The ADTAOFondation RTRA-STAE, ADTAO 2013 1

Acknowledgements

The ADTAO project

Is funded by RTRA-STAE

Is a 4 year project

Involves international experts : I.S. Duff, J.Mandel, A. Moore,Ph.L. Toint, L.N. Vicente,

Recruited 6 postdocs : J. Tshimanga, L. Seoane, W. Zerhouni, H.Varella, P. Jiranek, D. Titley-Peloquin

Is a collaboration between 5 entities : CERFACS, CNES, IRIT,Mteo-France, Obervatoire Midi-Pyrnes

Produced 25 journal papers, 2 international conferences, operationalsoftwares for NEMOVAR, GINS, ROMS, Arpege-IFS

Outline

Introduction to data assimilation

Dual iterative solvers

Summary and ongoing related work

Outline

Introduction to DA

A dynamical integration model predicts the state of the system given thestate at an earlier time.−→ integrating may lead to very large prediction errors−→ (inexact physics, discretization errors, approximated parameters)

Observational data are used to improve accuracy of the forecasts.−→ but the data are inaccurate (measurement noise, under-sampling)

Introduction to DA

A dynamical integration model predicts the state of the system given thestate at an earlier time.−→ integrating may lead to very large prediction errors−→ (inexact physics, discretization errors, approximated parameters)

Observational data are used to improve accuracy of the forecasts.−→ but the data are inaccurate (measurement noise, under-sampling)

Introduction to DA

Solve a large-scale non-linear weighted least-squares problem:

minx∈Rn

2‖x − xb‖2

B−1 +1

N∑j=0

∥∥Hj

(Mj (x)

)− yj

∥∥2

R−1j

x ≡ x(t0) is the control variable

Mj are model operators: x(tj ) =Mj (x(t0))

Hj are observation operators: yj ≈ Hj (x(tj ))

the obervations yj and the background xb are noisy

B and Rj are covariance matrices

Introduction to DA

Project desciption:

minx∈Rn

2‖x − xb‖2

B−1 +1

N∑j=0

∥∥Hj

(Mj (x)

)− yj

∥∥2

R−1j

Improving B : CERFACS and CNES, using diffusion operator andensemble techniques (Talks of L. Berre, A. Weaver)

Optimization algorithms : CERFACS, IRIT, CNES dual algorithmsand Ensemble Kalman filters (Talks of Ph. Toint, L. Vicente)

Modelling : CNES

Introduction to DA

minx∈Rn

2‖x − xb‖2

B−1 +1

N∑j=0

∥∥Hj

(Mj (x)

)− yj

∥∥2

R−1j

Typically solved using a truncated Gauss-Newton algorithm(known as 4D-Var in the DA community).

−→ linearize Hj

(Mj (x

(k) + δx (k)))≈ Hj

(Mj (x

+ H(k)j δx (k)

−→ solve the linearized subproblem

minδx(k)∈Rn

2‖δx (k) − (xb − x (k))‖2

B−1 +1

∥∥∥H(k)δx (k) − d (k)∥∥∥2

−→ update x (k+1) = x (k) + δx (k)

Introduction to DA

minx∈Rn

2‖x − xb‖2

B−1 +1

N∑j=0

∥∥Hj

(Mj (x)

)− yj

∥∥2

R−1j

Typically solved using a truncated Gauss-Newton algorithm(known as 4D-Var in the DA community).

−→ linearize Hj

(Mj (x

(k) + δx (k)))≈ Hj

(Mj (x

+ H(k)j δx (k)

−→ solve the linearized subproblem

minδx(k)∈Rn

2‖δx (k) − (xb − x (k))‖2

B−1 +1

∥∥∥H(k)δx (k) − d (k)∥∥∥2

−→ update x (k+1) = x (k) + δx (k)

Outline

Dual Approach

Exploiting the structure: Dual Approach

The exact solution can be rewritten from duality theory or using theSherman-Morrison-Woodbury formula

xb − xk + BHTk (HkBH

Tk + R)−1(dk − Hk (xb − xk ))︸︷︷︸

Lagrange mult. : requires solving a linear system iteratively in Rm

If m << n, then performing the minimization in Rm can reduce memory andcomputational cost.

Dual Approach

Tk + R)−1(dk − Hk (xb − xk ))︸︷︷︸

Dual Approach

Tk + R)−1(dk − Hk (xb − xk ))︸︷︷︸

Dual Approach

Preconditioned CG algorithm

Initialization

r0 = Aδx0 − b, z0 = Fr0, p0 = z0

For i = 0, 1, ...

1 qi = (B−1 + HTR−1H)pi

2 αi =< ri , zi > / < qi , pi > Compute the step-length

3 δxi+1 = δxi + αipi Update the iterate

4 ri+1 = ri − αiqi ; Update the residual

5 ri+1 = ri+1 − RZT ri+1 Re-orthogonalization

6 zi+1 = F ri+1 Update the preconditioned residual

7 βi =< ri+1, zi+1 > / < ri , zi > Ensure A-conjugate directions

8 R = [R, r/βi ] Re-orthogonalization

9 Z = [Z , z/βi ] Re-orthogonalization

10 pi+1 = zi+1 + βipi Update the descent direction

Dual Approach

Theorem

Suppose that

1 BHTG = FHT.

2 v0 = xb − x0.

→ vectors ri , pi , vi , zi and qi such that

ri = HTri ,

pi = BHTpi ,

vi = v0 + BHTvi ,

zi = BHTzi ,

qi = HTqi

Dual Approach

Initialization steps

given v0; r0 = (HTR−1H + B−1)v0 − b, . . .

Loop: WHILE

1 HTqi−1 = HT(R−1HB−1HT + Im)pi−1

2 αi−1 = rTi−1zi−1 / qTi−1pi−1

3 BHTvi = BHT(vi−1 + αi−1pi−1)

4 HTri = HT(ri−1 + αi−1qi−1)

5 BHTzi = FHTri = BHTGri FHT = BHTG

6 βi = (rTi zi / rTi−1zi−1)

7 BHTpi = BHT(−zi + βi pi−1)

Dual Approach

Initialization

λ0 = 0, r0 = R−1(d − H(xb − x)),z0 = Gr0, p1 = z0, k = 1

Loop on k

1 qi = Api

2 αi =< ri−1, zi−1 >C / < qi , pi >C

3 λi = λi−1 + αi pi

4 ri = ri−1 − αi qi

5 βi =< ri−1, zi−1 >C / <ri−2, zi−2 >C

6 zi = Gri

7 pi = zi−1 + βi pi−1

A = R−1HBHT + Im

G is the preconditioner.

C is the inner-product.

RPCG Algorithm: C = HBHT

identical CG on original system :preserves monotonic decrease ofquadratic cost and exploit geometry

G should be symmetric w.r.t. to C(FHT = BHTG)

Best known reference : PSASAlgorithm for C = R

Dual Approach

Initialization

λ0 = 0, r0 = R−1(d − H(xb − x)),z0 = Gr0, p1 = z0, k = 1

Loop on k

1 qi = Api

2 αi =< ri−1, zi−1 >C / < qi , pi >C

3 λi = λi−1 + αi pi

4 ri = ri−1 − αi qi

5 βi =< ri−1, zi−1 >C / <ri−2, zi−2 >C

6 zi = Gri

7 pi = zi−1 + βi pi−1

A = R−1HBHT + Im

G is the preconditioner.

C is the inner-product.

RPCG Algorithm: C = HBHT

identical CG on original system :preserves monotonic decrease ofquadratic cost and exploit geometry

G should be symmetric w.r.t. to C(FHT = BHTG)

Best known reference : PSASAlgorithm for C = R

Dual Approach

Observations: SST (Sea Surface Temperature) and SSH(Sea Surface Height) observationsfrom satellites. Sub-surface hydrographic observations from floats.

Number of observations (m): 105

Number of state variables (n): 106 for strong constraint and 107 for weak constraint.

Computation: 64 CPUs

Preconditioning in dual space

It is possible to maintain the one-to-one correspondance between primal and dualiterates, under the assumption that

Fk−1HTk = BHT

k Gk−1

where Fk−1 is a preconditioner for a primal solver and Gk−1 is a preconditioner fora dual solver (Gratton and Tshimanga 2009).

The preconditioner Gk−1 needs to be symmetric in HkBHTk inner product.

Use Preconditioned Conjugate Gradient method (PCG)

→ Preconditioning with the quasi-Newton Limited Memory Preconditioner(Morales and Nocedal 2000) (Gratton, Sartenaer and Tshimanga 2011)

For linear case, Gratton, Gurol and Toint (2012) derive the quasi-Newton LMP indual space which generates mathematically equivalent iterates to those of primalapproach.

The quasi-Newton LMP in dual space (Linear case)

The quasi-Newton LMP: The descent directions pi , i = 1, ..., l generated by a CGmethod are used.

(In −

pipTi A

pTi Api

)Fi−1

(In −

ApipTi

pTi Api

→ F = Fl .

The corresponding quasi-Newton preconditioner in dual space is given as

(Im −

pi pTi AC

pTi AC pi

)Gi−1

(Im −

Api pTi C

pTi AC pi

pi pTi C

pTi AC pi

where i = 1, ..., l , C = HBHT , A = Im + R−1HBHT and pi is the search direction.→ G = Gl .

→ This preconditioner satisfies the relation: FHT = BHTG and it is symmetric inthe C inner product (Gratton, Gurol and Toint 2012).

(In −

pipTi A

pTi Api

)Fi−1

(In −

ApipTi

pTi Api

→ F = Fl .

(Im −

pi pTi AC

pTi AC pi

)Gi−1

(Im −

Api pTi C

pTi AC pi

pi pTi C

pTi AC pi

(In −

pipTi A

pTi Api

)Fi−1

(In −

ApipTi

pTi Api

→ F = Fl .

(Im −

pi pTi AC

pTi AC pi

)Gi−1

(Im −

Api pTi C

pTi AC pi

pi pTi C

pTi AC pi

(In −

pipTi A

pTi Api

)Fi−1

(In −

ApipTi

pTi Api

→ F = Fl .

(Im −

pi pTi AC

pTi AC pi

)Gi−1

(Im −

Api pTi C

pTi AC pi

pi pTi C

pTi AC pi

The quasi-Newton LMP in dual space (Nonlinear case)

For nonlinear case, inheriting the previous preconditioner may not be possible!

Solution:

Re-generate the pairs and the preconditioner using the current inner product.

(Im −

pi pTi AC

pTi AC pi

)Gi−1

(Im −

Api pTi C

pTi AC pi

pi pTi C

pTi AC pi

where i = 1, ..., l , C = HBHT , A = Im + R−1HBHT and pi is the search direction.

→ It is costly for large-scale problems.

Define a criterion on whether we precondition the system or not by using ameasure on symmetry.

→ Sensitive to the threshold value.

Objective:

A robust algorithm that handles this sensitivity

A globally convergent algorithm

Most cases are not highly nonlinear : → Perturb as little as possible thepreconditioner of the linear case, and check a posteriori

Solution:

(Im −

pi pTi AC

pTi AC pi

)Gi−1

(Im −

Api pTi C

pTi AC pi

pi pTi C

pTi AC pi

Objective:

Solution:

(Im −

pi pTi AC

pTi AC pi

)Gi−1

(Im −

Api pTi C

pTi AC pi

pi pTi C

pTi AC pi

Objective:

Solution:

(Im −

pi pTi AC

pTi AC pi

)Gi−1

(Im −

Api pTi C

pTi AC pi

pi pTi C

pTi AC pi

Objective:

Solution:

(Im −

pi pTi AC

pTi AC pi

)Gi−1

(Im −

Api pTi C

pTi AC pi

pi pTi C

pTi AC pi

Objective:

Globally convergent algorithm in dual space

Global convergence can be ensured by inserting the Gauss-Newton strategy in atrust region framework.

Trust-region method simply solves the following problem at iteration k:

minδxk∈Rn

J(δxk ) =1

2‖δxk − xb + xk‖2

B−1 +1

2‖Hkδxk − dk‖2

subject to ‖δxk‖F−1k≤ ∆k (primal approach)

where ∆k is the trust region radius.

Trust-region in dual space

The preconditioner Gk−1 that is inherited from previous iteration may not besymmetric in the current inner product and may not be positive-definite in thefull dual space (merely in one direction).

We need to adapt the strategy in the trust region algorithm.

TR Step calculation with a flexible (Steihaug-Toint) RPCGalgorithm

1 Check the positive-definiteness along the steepest descent direction.

2 Compute the Cauchy step

3 Compute the step beyond the Cauchy step with the RPCG algorithm (ignoringsymmetry problem)

4 Backtrack along the CG path if needed

Flexible trust region algorithm

1 Initialization

2 Compute the step by the flexible (Steihaug Toint) RPCG algorithm

3 Accept the step beyond the Cauchy step if

f (yk ) < f (xCk )

4 Accept the trial point according to the ratio of achieved to predicted reduction

5 Update the trust region

→ The global convergence can be proved! (see S. Gurol PhD)

→ This approach is similar to the approach that computes the magical step proposed by(Conn, Gould, Toint 2000).

Flexible trust region algorithm

1 Initialization

2 Compute the step by the flexible (Steihaug Toint) RPCG algorithm

3 Accept the step beyond the Cauchy step if

f (yk ) < f (xCk )

4 Accept the trial point according to the ratio of achieved to predicted reduction

5 Update the trust region

→ The global convergence can be proved! (see S. Gurol PhD)

→ This approach is similar to the approach that computes the magical step proposed by(Conn, Gould, Toint 2000).

Numerical Results

Numerical experiment on heat equation (1/3)

The dynamical model is considered to be the nonlinear heat equation defined by

δt− δ2x

δu2− δ2x

δv 2+ f [x ] = 0 in Ω× (0,∞)

x [u, v , t] = 0 on δΩ× (0,∞)

where the temperature variable x [u, v , t] depend on both time t and position given byspatial coordinates u and v . The function f [x ] is defined by

f [x ] = exp[ηx ]

Numerical Results

f [x ] = exp[ηx ] η = 2

Numerical Results

f [x ] = exp[ηx ] η = 4.2

References

Conclusion

We developed and implemented a fast and robust preconditioned non-linear solverfor large-scale problems

The solver is implemented in operational systems in Meteorology andOceanography

Other techniques are used based on variant of Kalman filters : model reduction,ensemble algorithms

• S. Gratton, P. Toint and J. Tshimanga.Inexact range-space Krylov solvers for linear systems arising from inverse problems.SIAM Journal on Matrix Analysis and Applications, 32(3):969-986, 2011

• S. Gratton, P. Laloyaux, A. Sartenaer, and J. Tshimanga.A reduced and limited-memory preconditioned approach for the 4d-var data-assimilation problem. Q. J. Roy. Meteor. Soc.,137:452–466, 2011.

• S. Gratton and J. Tshimanga.An observation-space formulation of variational assimilation using a restricted preconditioned conjugate gradient algorithm. Q.J. Roy. Meterol. Soc., 135:1573–1585, 2009.

• J. Tshimanga, S. Gratton, A.T. Weaver, and A. Sartenaer.Limited-memory preconditioners with application to incremental four-dimensional variational data assimilation. Q. J. Roy.Meterol. Soc., 134:753–771, 2008.

• S. Gratton, S. Gurol, Ph.Toint. Preconditioning and Globalizing Conjugate Gradients in Dual Space for QuadraticallyPenalized Nonlinear-Least Squares Problems. Computational Optimization and Applications, 54(1), pp. 1-25, 2013.

• S. Gratton, J. Tshimanga and Ph. L. Toint. Conjugate-gradients versus multigrid solvers for diffusion-based correlationmodels in data assimilation. Quarterly Journal of the Royal Meteorological Society, to appear, 2013.

• S. Gratton and L. N. Vicente. A surrogate management framework using rigorous trust-region steps. Optimization Methodsand Software to appear, 2013.

Variationnal Data assimilation, Earth, Atmosphere, Ocean · Introduction to data assimilation Dual...

Documents

Assimilation de données d'humidité des sols pour la prévision de … · REVUE DES SCIENCES DE L'EAU, Rev. Sci. Eau 16/2(2003) 173-197 Assimilation de données d'humidité des sols

Journée Prévision Numérique du Temps, 10 Juin 2008Utilisation du GPS en météo 1 ASSIMILATION VARIATIONNELLE ET OPERATEURS DOBSERVATION COMPLEXES EN METEOROLOGIE

EnKFEnKF assimilation of mobile Doppler radar data collect ...hfip.psu.edu/EDA2010/Tanamachi.pdf · LLJ 0230 UTC VAD 0100 UTC VAD Heights are CAPE = in km AGL 4600 J kg-1 Comparison

du 30/11/16 au 02/12/16 à Grenoble, France The Analog Data · 3 Institut Mines-Télécom Data Assimilation: 2 points of view 01/12/16 Colloque National d’Assimilation de Données

Multiscale data assimilation approaches and error ...cerea.enpc.fr/fich/theses/theses_soutenues_2012/thesis_koohkan.pdf · I am also deeply grateful to my thesis committee, Dr Slimane

Les pieds-noirs - hommes-et-migrations.fr · Le peuplement de “l’Algérie française”s’est fait par assimilation de populations venues ... tude volontairement dévalorisante

PermonFLLOP PermonMultiBody PermonIneqsc15.supercomputing.org/sites/all/themes/SC15images/tech_poster/poster... · quadratic programming solvers application-specific modules PETSc

Data Visualization & Data Storytelling

Biostimulants, situation technique et réglementaire · fonction, quand appliqués aux plantes ou à la rhizosphère, ... Nutrition minérale et hydrique Substances humiques Assimilation

Modélisation Numérique de l’Écoulement Atmosphérique et ...gershwin.ens.fr/talagrand/downloads/Enseignement ED/Cours2014/Cours 5.pdfde l’Écoulement Atmosphérique ! et Assimilation

Overview of GNSS data assimilation at Météo-France...Cliquez pour modifier le style du titre Cliquez pour modifier le style des sous-titres du masque 1 Overview of GNSS data assimilation

Assimilation des armes biologiques aux programmes gouvernementaux offensifs Cours No. 6

Modélisation Numérique de l’Écoulement Atmosphérique et Assimilation de …gershwin.ens.fr/talagrand/downloads/Enseignement ED... · 2016-04-01 · de l’Écoulement Atmosphérique

Open data & linked data

La Confédération canadienne 1850-1890 Pressions ou Facteurs amenant à la Confédération Clergé Assimilation Nationalisme vs Impérialisme Guerre civile américaine

Atelier Marée barotrope Les Grenettes 2010. Champs d'investigation Validation atlas NEA ~50 ondes disponibles, ~20 ondes avec assimilation validation

Intégration-Assimilation 1830-1939. Introduction. Les mots ont une histoire Aujourdhui (J. Costa-Lascoux, de limmigré au citoyen, 1989) « Assimilation

Data assimilation of in situ and satellite remote …...Abstract. The understanding of physical dynamics is crucial to provide scientiﬁcally credible information on lake ecosys-tem

Assimilation des armes biologiques aux programmes gouvernementaux offensifs

Concours CNRS 2005 – Section 19 CR2 - Système terrestre: Enveloppes superficielles Ricci Sophie, Oral CNRS, 11 Mai 2005 Post-Doctorat - JPL: Assimilation