Principle of "double Lagrange"
===============================

The method proposed here is the one implemented in code CASTEM 2000 (personal communication from Th. CHARRAS and P. VERPEAUX). An intuitive layout could be as follows:

We can see that the dualized problem [:ref:`éq 2-4 <éq 2-4>`] has zero terms on the diagonal: those corresponding to Lagrange's degrees of freedom. This property is also noticeable on the Lagrangian [:ref:`éq 2-5 <éq 2-5>`]: there are no quadratic terms in :math:`\lambda`.

This nullity of diagonal terms prevents certain permutations of rows and columns: you cannot place a Lagrange before the physical degrees of freedom that it constrains.

The idea is then to break down each Lagrange coefficient :math:`\lambda` into 2 equal parts :math:`{\lambda }^{1}` and :math:`{\lambda }^{2}`. Equation :math:`\mathrm{Cu}=d` is then replaced by:

:math:`\begin{array}{}\mathrm{Cu}-\alpha ({\lambda }^{1}-{\lambda }^{2})=d\\ \mathrm{Cu}+\alpha ({\lambda }^{1}-{\lambda }^{2})=d\end{array}`

where :math:`\alpha` is a nonzero constant.

Let's show the equivalence of the old problem and the new one:

**Problem 1**: "simple Lagrange"

find :math:`\mathrm{\{}\begin{array}{c}\mathrm{u}\mathrm{\in }{\mathrm{ℝ}}^{n}\\ \lambda \mathrm{\in }{\mathrm{ℝ}}^{p}\end{array}` such as :math:`(S)\text{:}\mathrm{\{}\begin{array}{c}\text{Au}+{\mathrm{C}}^{\mathrm{T}}\lambda \mathrm{=}\mathrm{b}\\ \text{Cu}\mathrm{=}\mathrm{d}\end{array}`

:math:`(S)\iff \{\begin{array}{}{\lambda }^{1}={\lambda }^{2}\\ \lambda ={\lambda }^{1}+{\lambda }^{2}\\ \text{Au}+{C}^{T}\lambda =b\\ \text{Cu}=d\end{array}\iff \{\begin{array}{}\text{Au}+{C}^{T}{\lambda }^{1}+{C}^{T}{\lambda }^{2}=b\\ \text{Cu}-{\text{αλ}}^{1}+{\text{αλ}}^{2}=d\\ \text{Cu}+{\text{αλ}}^{1}-{\text{αλ}}^{2}=d\end{array}`

:math:`\alpha` is a :math:`\mathrm{\ne }0` constant

Hence the problem equivalent to the previous one:

**Problem 2**: "double Lagrange"

find :math:`\mathrm{\{}\begin{array}{c}\mathrm{u}\mathrm{\in }{\mathrm{ℝ}}^{n}\\ {\lambda }^{1},{\lambda }^{2}\mathrm{\in }{\mathrm{ℝ}}^{p}\mathrm{\times }{\mathrm{ℝ}}^{p}\end{array}` such as :math:`(\text{S'})\text{:}\mathrm{\{}\begin{array}{c}\text{Au}+{\mathrm{C}}^{\mathrm{T}}{\lambda }^{1}+{\mathrm{C}}^{\mathrm{T}}{\lambda }^{2}\mathrm{=}\mathrm{b}\\ \text{Cu}\mathrm{-}{\text{αλ}}^{1}+{\text{αλ}}^{2}\mathrm{=}\mathrm{d}\\ \text{Cu}+{\text{αλ}}^{1}\mathrm{-}{\text{αλ}}^{2}\mathrm{=}\mathrm{d}\end{array}`

The new problem can be written as:

:math:`\text{K'}\text{X'}=\text{F'}`

with:

:math:`\{\begin{array}{}X\text{'}=(u,{\lambda }_{1},{\lambda }_{2})\\ \text{F'}=(\text{b,}\text{d,}d)\end{array}`

:math:`\text{K'}=\left[\begin{array}{ccc}A& {C}^{T}& {C}^{T}\\ C& -\mathrm{\alpha l}& \mathrm{\alpha l}\\ C& \mathrm{\alpha l}& -\mathrm{\alpha l}\end{array}\right]`

The problem corresponds to making the functional extreme:

:math:`\begin{array}{}L\text{'}(u,{\lambda }^{1},{\lambda }^{2})=\frac{1}{2}(\text{Au,}u)-(\text{b,}u)+({\lambda }^{1},\text{Cu}-d)\\ +({\lambda }^{2},\text{Cu}-d)-\frac{\alpha }{2}({\lambda }^{1}-{\lambda }^{2},{\lambda }^{1}-{\lambda }^{2})\end{array}`

It can be shown (see Appendix 2) that if a certain rule for numbering unknowns is observed, and by choosing the constant :math:`\alpha >0`, the matrix :math:`\text{K'}` verifies the condition cond1.

This rule is as follows:

For a blocking relationship :math:`\text{Cu}-d=0`, it corresponds to 2 Lagrange multipliers :math:`{\lambda }^{1}` and :math:`{\lambda }^{2}`. This relationship involves a number of physical degrees of freedom.

**Rule** :math:`{R}_{0}`:

For each blocking relationship, :math:`{\lambda }^{1}` should be placed before the first degree of constrained physical freedom and :math:`{\lambda }^{2}` after the last degree of constrained physical freedom.

To reduce the memory occupancy of the matrix :math:`K`, it is necessary to try to minimize the width of the band. This is what we do in *Code_Aster* by "framing" relationships "as closely as possible": :math:`{\lambda }^{1}` is placed just before the first constrained degree of freedom, :math:`{\lambda }^{2}` is placed just after the last constrained ddl.

**Illustration:**

That's a problem with 4 physical degrees of freedom: :math:`{u}_{1}{\text{,u}}_{2}{\text{,u}}_{3}{\text{,u}}_{4}`.

This system is subject to 2 conditions:

:math:`\{\begin{array}{}{a}_{\text{11}}{u}_{1}+{a}_{\text{13}}{u}_{3}={b}_{1}\\ {a}_{\text{22}}{u}_{2}+{a}_{\text{24}}{u}_{4}={b}_{2}\end{array}`

Let's call :math:`{\lambda }_{1}^{1},{\lambda }_{1}^{2}` the 2 Lagrange degrees of freedom associated with the 1st condition and :math:`{\lambda }_{2}^{1},{\lambda }_{2}^{2}` those associated with the 2nd condition.

Assuming that the physical degrees of freedom have been numbered in the order: :math:`{u}_{1}{\text{,u}}_{2}{\text{,u}}_{3}{\text{,u}}_{4}`, the total numbering of the degrees of freedom retained by*Aster* is then:

:math:`{\lambda }_{1}^{1}\text{,}{u}_{1}\text{,}{\lambda }_{2}^{1}\text{,}{u}_{\mathrm{2,}}{u}_{\mathrm{3,}}{\lambda }_{1}^{2}\text{,}{u}_{4},{\lambda }_{2}^{2}`

:math:`{\lambda }_{1}^{1}` and :math:`{\lambda }_{1}^{2}` frame the constrained degrees of freedom "as closely as possible" (:math:`{u}_{1}` and :math:`{u}_{3}`)

:math:`{\lambda }_{2}^{1}` and :math:`{\lambda }_{1}^{2}` frame the constrained degrees of freedom "as closely as possible" (:math:`{u}_{2}` and :math:`{u}_{4}`)

The "double Lagrange" technique associated with rule :math:`{R}_{0}` therefore makes it possible to solve any physically well-posed linear system with the :math:`{\mathit{LDL}}^{T}` algorithm without permutation. However, the demonstration assumes that the **matrix** :math:`A` **is symmetric and positive** (not necessarily defined).

**Note:**

*The assumptions:* :math:`A` *symmetric and* :math:`A` *positive are required to use* :math:`{\mathit{LDL}}^{T}` *(or* :math:`\mathit{LU}` *) without permutation as shown by the following two counterexamples:*


* :math:`{A}_{1}=\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]` is symmetric but not positive,


* :math:`{A}_{2}=\left[\begin{array}{cc}0& 1\\ -1& 1\end{array}\right]` is positive but not symmetric.