PartitionedVectors.jl Tutorial
A PartitionedVector <: DenseVector <: AbstractVector wraps a PartitionedStructures.Elemental_pv, to make JuliaSmoothOptimizers modules able to exploit the partially separable structure. For now, PartitionedVector is the keystone to define PartiallySeparableNLPModels, and then to consequently:
- replace
Vectorin JSOSolvers.jl; - replace
Vectorin Krylov.jl; - make
LinearOperators relying only onPartitionedVectors viable; - fit the NLPModels interface (ex:
NLPModels.obj(nlp::PartiallySeparableNLPModel, x::PartitionedVector)see PartiallySeparableNLPModels.jl for more details).
Partitioned vectors usages are related to partially separable problems:
\[ f(x) = \sum_{i=1}^N f_i (U_i x) , \; f_i : \R^{n_i} \to \R, \; U_i \in \R^{n_i \times n},\; n_i \ll n,\]
whose inherit partitioned derivatives:
\[ \nabla f(x) = \sum_{i=1}^N U_i^\top \nabla f_i (U_i x) \quad \nabla^2 f(x) = \sum_{i=1}^N U_i^\top \nabla^2 f_i (U_i x) U_i,\]
where the set of $U_i$ gathers all the information related to the partitioned structure. We consider $U_i$ a linear application selecting the variable that parametrize the $i$-th element function $f_i$, each $U_i$ is defined from a vector of integers. The partially separable function
\[f(x) = f_1(x_1,x_2,x_3,x_4) + f_2(x_3,x_4,x_5,x_6) + f_3(x_5,x_6,x_7) + f_4(x_5,x_6,x_8)\]
get the following $U_i$:
U1 = [1, 2, 3, 4]
U2 = [3, 4, 5, 6]
U3 = [5, 6, 7]
U4 = [5, 6, 8]
Uis = [U1, U2, U3, U4]4-element Vector{Vector{Int64}}:
[1, 2, 3, 4]
[3, 4, 5, 6]
[5, 6, 7]
[5, 6, 8]However, before defining a PartitionedVector, you must understand the two usages of PartitionedVectors:
- usage 1: store each element contribution $\hat{v}_i$ independently and aggregate them to form $v = \sum_{i=1}^N U_i^\top \hat{v}_i$
In optimization methods, you use it to store $\nabla f_i (U_i x)$, $y_i = \nabla f_i (U_i x_{k+1}) - \nabla f_i (U_i x_k)$ or the result of a partitioned hessian-vector product which is a partitioned vector:
\[ \nabla^2 f(x_k) s \approx B_k s = (\sum_{i=1}^N U_i^\top B_{k,i} U_i ) s = \sum_{i=1}^N U_i^\top (B_{k,i} U_i s) .\]
- usage 2: represent simultaneously a vector $x \in \mathbb{R}^n$ and the application of every $U_i$ onto $x$: $U_i x, \forall i$.
By construction, the elements parametrized by the same variables (for exemple U1 and U3 are parametrized by the third variable) share the same values. In optimization methods, it allows to store the current point $x_k$ or step $s_k$, which always comes in handy to evaluate $f_i(U_i x), \nabla f_i(U_i x)$ or $B_{k,i} U_i s$.
Any methods exploiting partially separable concepts will have to manipulate both usages at the same time, in particular the solvers from JSOSolvers.jl and Krylov.jl. By default, you can define a PartitionedVector just from Uis as
using PartitionedVectors
pv = PartitionedVector(Uis)PartitionedVector{Float64}
[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]which will be of usage 1. If you want a vector for usage 2 you have to set simulate_vector optional argument to true
pv_vec = PartitionedVector(Uis; simulate_vector=true)PartitionedVector{Float64}
[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]The distinction between both is about how they form a Vector from them. For example:
pv .= pv_vec
pv == pv_vecwhich means that elements from pv are of same value than those of pv_vec. However, Vector(pv) relies on build! satisfying the specified usage and consequently
Vector(pv) != Vector(pv_vec)You can set a PartitionedVector of usage 2 from a Vector with
set!(pv_vec, rand(length(pv_vec)))PartitionedVector{Float64}
[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]Warning: the application set!() on PartitionedVector of usage 1 doesn't have sense, and produces an error.
PartitionedVectors.jl specify several methods from various modules. For operations that are not in place, the result will take usage 1.
Warning: you have to be careful when you mix both usages in a single operation, because the result may have no meaning. Keep in mind the result you expect for Vector(pv).
Base.jl:
- elementary operations
+, -, *, ==for PartitionedVectors.
pv + pv == 2 * pv
pv - pv == 0 * pvtrueMoreover, it supports the broadcast for the same operations (unfortunately not in place for now).
pv .+ pv == 2 .* pv
pv .- pv == 0 .* pvtrueSpecial case when both usages get the same Vector
pv .= 0
pv_vec .= pv
Vector(pv) == Vector(pv_vec)true- supports methods related to
AbstractArrays such as:get_index,set_index!refers to thei-th element vector ofpv
pv .= 1 pv[1]PartitionedStructures.ModElemental_ev.Elemental_elt_vec{Float64}([1.0, 1.0, 1.0, 1.0], [1, 2, 3, 4], 4)pv2 = pv - 0.5 * pv pv[1] = pv2[1] pv[1] == pv[2]falsefirstindex,lastindex,size,length:
firstindex(pv) == 1 lastindex(pv) == 4 size(pv) == (4,) length(pv) == 8
note that size and length differ,truelengthrefers to the biggest index (e.g. $n$) whilesizerefers to the number of elements $N$.copy,similar:
pvcopy = copy(pv) pvsimilar = similar(pv)PartitionedVector{Float64} [5.613e-321, NaN, 6.90521106230984e-310, 6.90521106676276e-310, 6.90516652495666e-310, 6.90520308147226e-310, 6.90516647740146e-310, 5.613e-321]
LinearAlgebra: both dot and norm rely on build!(::PartitionedVector) before applying dot or norm to the resulting Vector
using LinearAlgebra
dot(pv,pv) ≈ norm(pv)^2trueIn addition, PartitionedVectors.jl defines a:
LinearOperatorfrom aPartitionedMatrix(see PartitionedStructures.jl) relying onPartitionedVectors
using PartitionedStructures, LinearOperators
epm = PartitionedStructures.identity_epm(Uis)
lo = LinearOperators.LinearOperator(epm)
lo * pvPartitionedVector{Float64}
[6.9052076868676e-310, 6.9052076868676e-310, 6.9052076868676e-310, 6.9052076868676e-310, 6.9052076868676e-310, 6.9052076868676e-310, 6.9052076868676e-310, 6.9052076868676e-310]Note: Matrix(lo) will produce an error, since the default implementation assumes a complete Vector-like behaviour.
- dedicated
CgWorkspacefrom Krylov.jl to solve a partitioned linear system (from a partitionedLinearOperator).
using Krylov # 0.9.0
solver = Krylov.CgWorkspace(pv)
pv_gradient = similar(pv)
(N,) = size(pv)
for i = 1:N
nie = pv_gradient[i].nie #size of a element vector
pv_gradient[i] = rand(nie)
end
Krylov.krylov_solve!(solver, lo, -pv_gradient)┌──────────────────┬──────────────────────────┬──────────────────┐
│ CgWorkspace│ nrows: 8│ ncols: 8│
├──────────────────┼──────────────────────────┼──────────────────┤
│Precision: Float64│ Architecture: CPU / GPU│Storage: 204 bytes│
├──────────────────┼──────────────────────────┼──────────────────┤
│ Attribute│ Type│ Size│
├──────────────────┼──────────────────────────┼──────────────────┤
│ m│ Int64│ 8 bytes│
│ n│ Int64│ 8 bytes│
│ Δx│PartitionedVector{Float64}│ 16 bytes│
│ x│PartitionedVector{Float64}│ 16 bytes│
│ r│PartitionedVector{Float64}│ 16 bytes│
│ npc_dir│PartitionedVector{Float64}│ 16 bytes│
│ p│PartitionedVector{Float64}│ 16 bytes│
│ Ap│PartitionedVector{Float64}│ 16 bytes│
│ z│PartitionedVector{Float64}│ 16 bytes│
│ warm_start│ Bool│ 1 byte│
│ stats│Krylov.SimpleStats{Float64}│ 75 bytes│
└──────────────────┴──────────────────────────┴──────────────────┘
SimpleStats
niter: 3
solved: true
inconsistent: false
indefinite: false
npcCount: 0
residuals: []
Aresiduals: []
κ₂(A): []
allocation timer: 0.69μs
timer: 37.53ms
status: solution good enough given atol and rtol