Documentation

Averaging.OpportunisticGood

Non-ephemeral good nodes: the deterministic part of Lemma 4.2 #

Fix a reference state x₁ (the state at the start t₁ of the phase) and a threshold θ. The deviation of a later state x at v is r_v = x_v - α - β₁ χ_v, where α is the (conserved) average and β₁ χ the cut component of x₁; v is bad (badSet) if r_v² > θ. A round is bad (IsBadStep) if its dart crosses the cut or has a bad endpoint.

def Averaging.Opportunistic.IsCrossDart {V : Type u_1} {G : SimpleGraph V} (V₁ : Finset V) (e : G.Dart) :

A dart crossing the cut.

Equations
Instances For
    noncomputable def Averaging.Opportunistic.devVec {V : Type u_1} [Fintype V] [DecidableEq V] (V₁ : Finset V) (x₁ x : V → ℝ) (v : V) :

    The deviation r_v = x_v - α - β₁ χ_v of x from the reference x₁ (Lemma 4.2).

    Equations
    Instances For
      noncomputable def Averaging.Opportunistic.badSet {V : Type u_1} [Fintype V] [DecidableEq V] (V₁ : Finset V) (θ : ℝ) (x₁ x : V → ℝ) :

      The nodes with r_v² > θ.

      Equations
      Instances For
        def Averaging.Opportunistic.IsBadStep {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} (V₁ : Finset V) (θ : ℝ) (x₁ x : V → ℝ) (e : G.Dart) :

        A bad round: the dart crosses the cut or has a bad endpoint.

        Equations
        • One or more equations did not get rendered due to their size.
        Instances For
          @[implicit_reducible]
          noncomputable instance Averaging.Opportunistic.instDecidableIsBadStep {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} (V₁ : Finset V) (θ : ℝ) (x₁ x : V → ℝ) (e : G.Dart) :
          Decidable (IsBadStep V₁ θ x₁ x e)
          Equations
          theorem Averaging.Opportunistic.cutVec_eq_of_not_cross {V : Type u_1} [DecidableEq V] {G : SimpleGraph V} {V₁ : Finset V} {e : G.Dart} (h : ¬IsCrossDart V₁ e) :
          cutVec V₁ e.toProd.1 = cutVec V₁ e.toProd.2
          theorem Averaging.Opportunistic.avgRun_take_succ {V : Type u_1} [DecidableEq V] {G : SimpleGraph V} (x : V → ℝ) (l : List G.Dart) {k : ℕ} {e : G.Dart} (he : l[k]? = some e) :
          avgRun G x (List.take (k + 1) l) = edgeAvg G (avgRun G x (List.take k l)) e
          theorem Averaging.Opportunistic.devVec_edgeAvg {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} {V₁ : Finset V} (x₁ x : V → ℝ) (e : G.Dart) (v : V) :
          devVec V₁ x₁ (edgeAvg G x e) v = if v = e.toProd.1 ∨ v = e.toProd.2 then (x e.toProd.1 + x e.toProd.2) / 2 - Dynamics.avg x₁ - cutCoef V₁ x₁ * cutVec V₁ v else devVec V₁ x₁ x v

          The deviation at an untouched node does not change, and at the two endpoints of an internal dart it becomes the average of the two deviations.

          theorem Averaging.Opportunistic.not_mem_badSet_avgRun {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} {V₁ : Finset V} (θ : ℝ) (x₁ : V → ℝ) (v : V) (l : List G.Dart) (h0 : v ∉ badSet V₁ θ x₁ x₁) (hstep : ∀ k < l.length, ∀ (e : G.Dart), l[k]? = some e → v = e.toProd.1 ∨ v = e.toProd.2 → ¬IsBadStep V₁ θ x₁ (avgRun G x₁ (List.take k l)) e) (k : ℕ) :
          k ≤ l.length → v ∉ badSet V₁ θ x₁ (avgRun G x₁ (List.take k l))

          Good nodes stay good (proof of Lemma 4.2): a node that is not bad at the start and is touched only by rounds that are not bad is never bad.

          The endpoints of the k-th dart of l (empty past the end).

          Equations
          Instances For
            def Averaging.Opportunistic.IsBadRound {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} (V₁ : Finset V) (θ : ℝ) (x₁ : V → ℝ) (l : List G.Dart) (k : ℕ) :

            The k-th round of l is bad.

            Equations
            Instances For
              theorem Averaging.Opportunistic.card_touched_le {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} {V₁ : Finset V} (θ : ℝ) (x₁ : V → ℝ) (l : List G.Dart) :
              {v : V | v ∈ badSet V₁ θ x₁ x₁ ∨ ∃ k < l.length, ∃ (e : G.Dart), l[k]? = some e ∧ (v = e.toProd.1 ∨ v = e.toProd.2) ∧ IsBadStep V₁ θ x₁ (avgRun G x₁ (List.take k l)) e}.card ≤ (badSet V₁ θ x₁ x₁).card + 2 * {k ∈ Finset.range l.length | IsBadRound V₁ θ x₁ l k}.card

              Counting: the nodes that are bad at the start or touched by a bad round number at most |B| + 2 Z.