Skip to main content

Module partition

Module partition 

Source
Expand description

§Chapter 5.8.5 — Block partitions

New with task L1.7a (PLAN.md trilha L): the contract’s BlockPartition.

§Purpose

The matrices of optimization are assembled from blocks, and the code around them keeps asking where a block begins: the simplex method prices the structural columns of [A | ±I] and treats the logical ones apart (Chapter 5.1); the interior-point method stacks [−D Aᵀ; A δI] and must know that row n + i is the dual of constraint i (Chapter 5.14, KktForm::Augmented); a decomposition (Dantzig–Wolfe, Benders) names coupling rows and subproblem blocks. The matrix stays one CscMatrix; a BlockPartition is the small companion object that records the boundaries of its row and column blocks, so that assembly with Triplets, extraction and bookkeeping agree on them instead of each recomputing n + i.

§Notation

An m × n matrix is partitioned into p ≥ 0 row blocks and q ≥ 0 column blocks by the boundary lists

row_blocks = [r_0, r_1, …, r_p],  0 = r_0 < r_1 < … < r_p = m,
col_blocks = [c_0, c_1, …, c_q],  0 = c_0 < c_1 < … < c_q = n.

Row block k is the half-open range r_k..r_{k+1}; column block l is c_l..c_{l+1}; block (k, l) is their product. Strict increase means a block is never empty; a dimension of size 0 has the single boundary list [0] and no block. Two partitions of the same matrix are equal iff their lists are.

The two examples of the contract:

  • the computational form [A | ±I] of the simplex, A ∈ R^{m×n}: one row block, row_blocks = [0, m], and two column blocks, col_blocks = [0, n, n + m] — column j is structural iff col_block_of(j) = 0;
  • the augmented system K = [−D Aᵀ; A δI] of order n + m: row_blocks = col_blocks = [0, n, n + m] — the primal block first, as KktForm::Augmented requires.

§Algorithm B (Block of an index)

Given a boundary list b = [b_0, …, b_p] and an index 0 ≤ i < b_p.

B1. Find, by binary search, the number k of boundaries ≤ i (partition_point): k ≥ 1 since b_0 = 0 ≤ i, and k ≤ p since i < b_p. B2. Return k − 1: the block b_{k−1}..b_k contains i.

Cost O(log p).

§Invariants

(B1) row_blocks is non-empty, starts at 0 and is strictly increasing; its last element is m. (B2) The same for col_blocks and n. (B3) m ≤ u32::MAX and n ≤ u32::MAX: the dimensions fit the index space of the containers ((C4) of Chapter 5.8).

Checked by BlockPartition::check_invariants; both constructors return the first violation as a SparseError. The fields are public, as in the contract; a value edited by hand should be checked again.

§References

Maros, Computational Techniques of the Simplex Method (2003), §5.1 (the computational form); Wright, Primal-Dual Interior-Point Methods (1997), ch. 11 (the augmented system); the contract of the crate (BlockPartition).

Structs§

BlockPartition
Block boundaries of a partitioned matrix: row_blocks and col_blocks are boundary lists starting at 0 and ending at m, n (invariants (B1)–(B3)).