use faer::dyn_stack::{MemBuffer, MemStack};
use faer::linalg::cholesky::llt_pivoting::factor::{cholesky_in_place, cholesky_in_place_scratch};
use faer::{Mat, Par};
use crate::measurement::Measurement;
use crate::types::Bus;
use super::SeNetwork;
use super::jacobian::{StateLayout, measurement_jacobian};
pub const DENSE_LIMIT: usize = 2000;
pub const RANK_TOLERANCE: f64 = 1e-10;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Quantity {
Angle,
Magnitude,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Unknown {
pub bus: usize,
pub quantity: Quantity,
}
#[derive(Clone, Debug)]
pub struct ObservabilityReport {
pub n_unknowns: usize,
pub rank: usize,
pub structurally_unmeasured: Vec<Unknown>,
pub unobservable: Vec<Unknown>,
pub skipped_numerical: bool,
pub de_energized: Vec<Unknown>,
pub global_current_without_angle_reference: bool,
}
impl ObservabilityReport {
pub fn is_observable(&self) -> bool {
self.rank + self.de_energized.len() == self.n_unknowns
&& self.structurally_unmeasured.is_empty()
}
}
fn describe(layout: &StateLayout, col: usize) -> Unknown {
let magnitude_start = layout.vmag(0);
if col >= magnitude_start {
Unknown {
bus: col - magnitude_start,
quantity: Quantity::Magnitude,
}
} else {
let bus = (0..layout.n_buses)
.find(|&b| layout.theta(b) == Some(col))
.expect("angle column belongs to some bus");
Unknown {
bus,
quantity: Quantity::Angle,
}
}
}
fn pivoted_cholesky_rank(mut a: Mat<f64>, tol: f64) -> Option<(usize, Vec<usize>)> {
let n = a.nrows();
if n == 0 {
return Some((0, Vec::new()));
}
let mut perm = vec![0usize; n];
let mut perm_inv = vec![0usize; n];
let mut buffer = MemBuffer::new(cholesky_in_place_scratch::<usize, f64>(
n,
Par::Seq,
Default::default(),
));
let stack = MemStack::new(&mut buffer);
let (info, _) = cholesky_in_place(
a.as_mut(),
&mut perm,
&mut perm_inv,
Par::Seq,
stack,
Default::default(),
)
.ok()?;
let pivots: Vec<f64> = (0..info.rank).map(|k| a[(k, k)] * a[(k, k)]).collect();
let largest = pivots.iter().copied().fold(0.0f64, f64::max);
let rank = if largest <= 0.0 {
0
} else {
pivots.iter().take_while(|&&p| p > tol * largest).count()
};
Some((rank, perm))
}
pub fn analyze(
measurements: &[Measurement],
buses: &[Bus],
net: &SeNetwork,
layout: &StateLayout,
constraints: &crate::se::constraints::Constraints,
) -> ObservabilityReport {
let n = layout.n_unknowns();
let mut rows = measurement_jacobian(measurements, buses, net, layout);
let mut weights: Vec<f64> = measurements.iter().map(|m| m.weight()).collect();
let (_, constraint_rows) = constraints.evaluate(buses, net, layout);
let n_constraints = constraint_rows.len();
rows.extend(constraint_rows);
weights.extend(std::iter::repeat_n(1.0, n_constraints));
let has_global_current = measurements.iter().any(|m| {
matches!(
m.target,
crate::measurement::Target::BranchTerminalCurrent {
frame: crate::measurement::AngleFrame::Global,
..
}
) && m.weight() > 0.0
});
let has_voltage_angle = measurements
.iter()
.any(|m| m.kind == crate::measurement::MeasurementKind::VoltageAngle && m.weight() > 0.0);
let global_current_without_angle_reference = has_global_current && !has_voltage_angle;
let mut touched = vec![false; n];
for row in &rows {
for &(c, v) in row {
if v != 0.0 {
touched[c] = true;
}
}
}
let live = |u: &Unknown| net.energized.get(u.bus).copied().unwrap_or(true);
let de_energized: Vec<Unknown> = (0..n)
.map(|c| describe(layout, c))
.filter(|u| !live(u))
.collect();
let untouched = (0..n).filter(|&c| !touched[c]).count();
let structurally_unmeasured: Vec<Unknown> = (0..n)
.filter(|&c| !touched[c])
.map(|c| describe(layout, c))
.filter(live)
.collect();
if n > DENSE_LIMIT {
return ObservabilityReport {
n_unknowns: n,
rank: n - untouched,
structurally_unmeasured,
unobservable: Vec::new(),
de_energized,
skipped_numerical: true,
global_current_without_angle_reference,
};
}
let mut g = Mat::<f64>::zeros(n, n);
for (row, &w) in rows.iter().zip(&weights) {
if !w.is_finite() || w == 0.0 {
continue;
}
for &(i, hi) in row {
for &(j, hj) in row {
g[(i, j)] += w * hi * hj;
}
}
}
let Some((rank, perm)) = pivoted_cholesky_rank(g, RANK_TOLERANCE) else {
return ObservabilityReport {
n_unknowns: n,
rank: 0,
structurally_unmeasured,
unobservable: (0..n).map(|c| describe(layout, c)).filter(live).collect(),
de_energized,
skipped_numerical: false,
global_current_without_angle_reference,
};
};
let unobservable = perm[rank..]
.iter()
.map(|&c| describe(layout, c))
.filter(live)
.collect();
ObservabilityReport {
n_unknowns: n,
rank,
structurally_unmeasured,
unobservable,
de_energized,
skipped_numerical: false,
global_current_without_angle_reference,
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::branch_flow::Terminal;
use crate::measurement::{MeasurementKind, Target};
use crate::se::constraints::Constraints;
fn m(kind: MeasurementKind, target: Target) -> Measurement {
Measurement {
kind,
target,
value: 0.0,
sigma: 0.01,
}
}
fn mat(rows: &[&[f64]]) -> Mat<f64> {
let n = rows.len();
let mut m = Mat::<f64>::zeros(n, n);
for (i, row) in rows.iter().enumerate() {
for (j, &v) in row.iter().enumerate() {
m[(i, j)] = v;
}
}
m
}
#[test]
fn identity_is_full_rank() {
let (rank, _) = pivoted_cholesky_rank(mat(&[&[1.0, 0.0], &[0.0, 1.0]]), RANK_TOLERANCE)
.expect("factorizable");
assert_eq!(rank, 2);
}
#[test]
fn rank_one_outer_product_is_rank_one() {
let v = [1.0, 2.0, -1.0];
let rows: Vec<Vec<f64>> = (0..3)
.map(|i| (0..3).map(|j| v[i] * v[j]).collect())
.collect();
let refs: Vec<&[f64]> = rows.iter().map(|r| r.as_slice()).collect();
let (rank, _) = pivoted_cholesky_rank(mat(&refs), RANK_TOLERANCE).expect("factorizable");
assert_eq!(rank, 1, "v v^T has rank 1");
}
#[test]
fn rank_detection_is_scale_free() {
let (rank, _) = pivoted_cholesky_rank(mat(&[&[1e-12, 0.0], &[0.0, 1e-12]]), RANK_TOLERANCE)
.expect("factorizable");
assert_eq!(rank, 2);
}
#[test]
fn well_measured_system_is_observable() {
let (net, buses) = crate::se::tests::two_bus_net();
let measurements = vec![
m(MeasurementKind::VoltageMagnitude, Target::Bus(0)),
m(MeasurementKind::VoltageMagnitude, Target::Bus(1)),
m(MeasurementKind::ActivePower, Target::Bus(1)),
m(MeasurementKind::ReactivePower, Target::Bus(1)),
m(
MeasurementKind::ActivePower,
Target::BranchTerminal {
branch: 0,
terminal: Terminal::From,
},
),
];
let layout = StateLayout::new(&buses, &measurements, &net);
let report = analyze(
&measurements,
&buses,
&net,
&layout,
&Constraints::from_flags(&[]),
);
assert!(
report.is_observable(),
"expected observable, got {report:?}"
);
assert_eq!(report.rank, report.n_unknowns);
}
#[test]
fn a_zero_injection_constraint_makes_state_observable() {
let (net, buses) = crate::se::tests::two_bus_net();
let measurements = vec![
m(MeasurementKind::VoltageMagnitude, Target::Bus(0)),
m(MeasurementKind::VoltageMagnitude, Target::Bus(1)),
];
let layout = StateLayout::new(&buses, &measurements, &net);
let without = analyze(
&measurements,
&buses,
&net,
&layout,
&Constraints::from_flags(&[]),
);
assert!(
!without.is_observable(),
"the fixture must be under-determined without help"
);
let mut flags = vec![false; buses.len()];
flags[1] = true;
let with = analyze(
&measurements,
&buses,
&net,
&layout,
&Constraints::from_flags(&flags),
);
assert!(
with.rank > without.rank,
"a zero-injection constraint determined nothing: rank {} vs {}",
with.rank,
without.rank
);
}
#[test]
fn constraints_never_lower_the_reported_rank() {
let (net, buses) = crate::se::tests::two_bus_net();
let measurements = vec![
m(MeasurementKind::VoltageMagnitude, Target::Bus(0)),
m(MeasurementKind::VoltageMagnitude, Target::Bus(1)),
m(MeasurementKind::ActivePower, Target::Bus(1)),
m(MeasurementKind::ReactivePower, Target::Bus(1)),
];
let layout = StateLayout::new(&buses, &measurements, &net);
let bare = analyze(
&measurements,
&buses,
&net,
&layout,
&Constraints::from_flags(&[]),
);
let mut flags = vec![false; buses.len()];
flags[1] = true;
let constrained = analyze(
&measurements,
&buses,
&net,
&layout,
&Constraints::from_flags(&flags),
);
assert!(constrained.rank >= bare.rank);
assert!(constrained.structurally_unmeasured.len() <= bare.structurally_unmeasured.len());
}
#[test]
fn under_measured_system_names_what_is_missing() {
let (net, buses) = crate::se::tests::two_bus_net();
let measurements = vec![m(MeasurementKind::VoltageMagnitude, Target::Bus(0))];
let layout = StateLayout::new(&buses, &measurements, &net);
let report = analyze(
&measurements,
&buses,
&net,
&layout,
&Constraints::from_flags(&[]),
);
assert!(!report.is_observable());
assert_eq!(report.rank, 1, "only the measured magnitude is determined");
assert_eq!(report.unobservable.len(), report.n_unknowns - 1);
assert!(
!report.unobservable.contains(&Unknown {
bus: 0,
quantity: Quantity::Magnitude
}),
"the measured quantity must not be reported unobservable: {report:?}"
);
}
#[test]
fn structurally_complete_but_rank_deficient_is_caught() {
let (net, buses) = crate::se::tests::two_bus_net();
let measurements = vec![
m(
MeasurementKind::ActivePower,
Target::BranchTerminal {
branch: 0,
terminal: Terminal::From,
},
),
m(
MeasurementKind::ReactivePower,
Target::BranchTerminal {
branch: 0,
terminal: Terminal::From,
},
),
];
let layout = StateLayout::new(&buses, &measurements, &net);
let report = analyze(
&measurements,
&buses,
&net,
&layout,
&Constraints::from_flags(&[]),
);
assert_eq!(report.n_unknowns, 3);
assert!(
report.structurally_unmeasured.is_empty(),
"every unknown is reached by a measurement, so structure alone sees no problem: {report:?}"
);
assert_eq!(
report.rank, 2,
"two measurements cannot determine three unknowns"
);
assert!(!report.is_observable());
assert_eq!(report.unobservable.len(), 1);
}
#[test]
fn a_duplicate_measurement_adds_no_rank() {
let (net, buses) = crate::se::tests::two_bus_net();
let flow = m(
MeasurementKind::ActivePower,
Target::BranchTerminal {
branch: 0,
terminal: Terminal::From,
},
);
let measurements = vec![
flow,
m(
MeasurementKind::ReactivePower,
Target::BranchTerminal {
branch: 0,
terminal: Terminal::From,
},
),
flow,
];
let layout = StateLayout::new(&buses, &measurements, &net);
let report = analyze(
&measurements,
&buses,
&net,
&layout,
&Constraints::from_flags(&[]),
);
assert_eq!(
measurements.len(),
report.n_unknowns,
"as many rows as unknowns"
);
assert_eq!(report.rank, 2, "but only two of them are independent");
assert!(!report.is_observable(), "{report:?}");
}
#[test]
fn pinned_reference_makes_angles_observable() {
let (net, buses) = crate::se::tests::two_bus_net();
let measurements = vec![
m(MeasurementKind::VoltageMagnitude, Target::Bus(0)),
m(MeasurementKind::VoltageMagnitude, Target::Bus(1)),
m(
MeasurementKind::ActivePower,
Target::BranchTerminal {
branch: 0,
terminal: Terminal::From,
},
),
m(
MeasurementKind::ReactivePower,
Target::BranchTerminal {
branch: 0,
terminal: Terminal::From,
},
),
];
let layout = StateLayout::new(&buses, &measurements, &net);
assert!(
layout.angle_ref.is_some(),
"no angle measured, so one is pinned"
);
let report = analyze(
&measurements,
&buses,
&net,
&layout,
&Constraints::from_flags(&[]),
);
assert!(report.is_observable(), "{report:?}");
}
}