Module DictVectors

Module that provides concrete implementations of the AbstractDVec interface.

• DVec: basic AbstractDVec
• PDVec: parallel AbstractDVec with MPI and initiator support
• InitiatorDVec: allows storing information about initiator status

See Interfaces.

AbstractDVec{K,V}

Abstract data type for vector-like data structures with sparse storage. While conceptually AbstractDVecs represent elements of a vector space over a scalar type V, they are indexed by an arbitrary type K (could be non-integers) similar to dictionaries. They support the interface from VectorInterface.jl and are designed to work well for quantum Monte Carlo with lomc! and for matrix-free linear algebra with KrylovKit.

Concrete implementations are available as PDVec, DVec, and InitiatorDVec.

AbstractDVecs have a StochasticStyle which selects the spawning algorithm in FCIQMC. Looking up an element that is not stored in the AbstractDVec should return a zero, and setting a value to zero should remove it from the vector. To iterate over an AbstractDVec, use keys, pairs, or values. When possible, use reduction functions such as sum or mapreduce.

Interface

The interface is similar to the AbstractDict interface, but with the changed behaviour as noted above. Implement what would be needed for the AbstractDict interface (pairs, keys, values, setindex!, getindex, delete!, length, empty, empty!) and, in addition:

• StochasticStyle
• storage returns an AbstractDict storing the raw data with possibly different valtype than V.
• deposit!

A default implementation for the VectorInterface.jl interface is provided through the above functions.

See also DictVectors, Interfaces.

DVec{K,V,D<:AbstractDict{K,V},S}

Dictionary-based vector-like data structure for use with FCIQMC and KrylovKit. While mostly behaving like a Dict, it supports various linear algebra operations such as norm and dot. It has a StochasticStyle that is used to select an appropriate spawning strategy in the FCIQMC algorithm.

See also: AbstractDVec, InitiatorDVec, PDVec.

Constructors

• DVec(dict::AbstractDict[; style, capacity]): create a DVec with dict for storage. Note that the data may or may not be copied.

• DVec(args...[; style, capacity]): args... are passed to the Dict constructor. The Dict is used for storage.

• DVec{K,V}([; style, capacity]): create an empty DVec{K,V}.

• DVec(dv::AbstractDVec[; style, capacity]): create a DVec with the same contents as adv. The style is inherited from dv by default.

The default style is selected based on the DVec's valtype (see default_style). If a style is given and the valtype does not match the style's eltype, the values are converted to an appropriate type.

The capacity argument is optional and sets the initial size of the DVec via Base.sizehint!.

Examples

julia> dv = DVec(:a => 1)
DVec{Symbol,Int64} with 1 entry, style = IsStochasticInteger{Int64}()
  :a => 1

julia> dv = DVec(:a => 2, :b => 3; style=IsDeterministic())
DVec{Symbol,Float64} with 2 entries, style = IsDeterministic{Float64}()
  :a => 2.0
  :b => 3.0

InitiatorDVec{K,V} <: AbstractDVec{K,V}

Dictionary-based vector-like data structure for use with lomc! and KrylovKit.jl. See AbstractDVec. Functionally identical to DVec, but contains InitiatorValues internally in order to facilitate initiator methods. Initiator methods for controlling the Monte Carlo sign problem were first introduced in J. Chem. Phys. 132, 041103 (2010). How the initiators are handled is controlled by specifying an InitiatorRule with the initiator keyword argument (see below).

See also: AbstractDVec, DVec, PDVec.

Constructors

• InitiatorDVec(dict::AbstractDict[; style, initiator, capacity]): create an InitiatorDVec with dict for storage. Note that the data may or may not be copied.

• InitiatorDVec(args...[; style, initiator, capacity]): args... are passed to the Dict constructor. The Dict is used for storage.

• InitiatorDVec{K,V}([; style, initiator, capacity]): create an empty InitiatorDVec{K,V}.

• InitiatorDVec(dv::AbstractDVec[; style, initiator, capacity]): create an InitiatorDVec with the same contents as dv. The style is inherited from dv by default.

Keyword arguments

• style: A valid StochasticStyle. The default is selected based on the InitiatorDVec's valtype (see default_style). If a style is given and the valtype does not match the style's eltype, the values are converted to an appropriate type.

• initiator = Initiator(1): A valid InitiatorRule. See Initiator.

• capacity: Indicative size as Int. Optional. Sets the initial size of the InitiatorDVec via Base.sizehint!.

PDVec{K,V}(; kwargs...)
PDVec(iter; kwargs...)
PDVec(pairs...; kwargs...)

Dictionary-based vector-like data structure for use with FCIQMC and KrylovKit.jl. While mostly behaving like a Dict, it supports various linear algebra operations such as norm and dot, and the interface defined in VectorInterface.

The P in PDVec stands for parallel. PDVecs perform mapreduce, foreach, and various linear algebra operations in a threaded manner. If MPI is available, these operations are automatically distributed as well. As such it is not recommended to iterate over pairs, keys, or values directly unless explicitly performing them on the localpart of the vector.

See also: AbstractDVec, DVec, InitiatorDVec.

Keyword arguments

• style =default_style(V): A StochasticStyle that is used to select the spawning strategy in the FCIQMC algorithm.

• initiator =NonInitiator(): An InitiatorRule, used in FCIQMC to remove the sign problem.

• communicator: A Communicator that controls how operations are performed when using MPI. The defaults are NotDistributed when not using MPI and PointToPoint when using MPI.

Extended Help

Segmentation

The vector is split into Threads.nthreads() subdictionaries called segments. Which dictionary a key-value pair is mapped to is determined by the hash of the key. The purpose of this segmentation is to allow parallel processing - functions such as mapreduce, add! or dot (full list below) process each subdictionary on a separate thread.

Example

julia> add = FermiFS2C((1,1,0,0), (0,0,1,1));

julia> op = HubbardMom1D(add; t=4/π^2, u=4);

julia> pv = PDVec(add => 1.0)
1-element PDVec: style = IsDeterministic{Float64}()
  fs"|↑↑↓↓⟩" => 1.0

julia> pv = op * pv
7-element PDVec: style = IsDeterministic{Float64}()
  fs"|↑↓↑↓⟩" => 1.0
  fs"|↑↑↓↓⟩" => 4.0
  fs"|↓↑↓↑⟩" => 1.0
  fs"|↓↑↑↓⟩" => -1.0
  fs"|⇅⋅⋅⇅⟩" => 1.0
  fs"|↑↓↓↑⟩" => -1.0
  fs"|⋅⇅⇅⋅⟩" => 1.0

julia> map!(x -> -x, values(pv)); pv
7-element PDVec: style = IsDeterministic{Float64}()
  fs"|↑↓↑↓⟩" => -1.0
  fs"|↑↑↓↓⟩" => -4.0
  fs"|↓↑↓↑⟩" => -1.0
  fs"|↓↑↑↓⟩" => 1.0
  fs"|⇅⋅⋅⇅⟩" => -1.0
  fs"|↑↓↓↑⟩" => 1.0
  fs"|⋅⇅⇅⋅⟩" => -1.0

julia> dest = similar(pv)
0-element PDVec: style = IsDeterministic{Float64}()

julia> map!(x -> x + 2, dest, values(pv))
7-element PDVec: style = IsDeterministic{Float64}()
  fs"|↑↓↑↓⟩" => 1.0
  fs"|↑↑↓↓⟩" => -2.0
  fs"|↓↑↓↑⟩" => 1.0
  fs"|↓↑↑↓⟩" => 3.0
  fs"|⇅⋅⋅⇅⟩" => 1.0
  fs"|↑↓↓↑⟩" => 3.0
  fs"|⋅⇅⇅⋅⟩" => 1.0

julia> sum(values(pv))
-6.0

julia> dot(dest, pv)
10.0

julia> dot(dest, op, pv)
44.0

MPI

When MPI is active, all parallel reductions are automatically reduced across MPI ranks with a call to MPI.Allreduce.

In a distributed setting, PDVec does not support iteration without first making it explicit the iteration is only to be performed on the local segments of the vector. This is done with localpart. In general, even when not using MPI, it is best practice to use localpart when explicit iteration is required.

Use with KrylovKit

PDVec is compatible with eigsolve from KrylovKit.jl. When used, the diagonalisation is performed in a threaded and distributed manner. Using multiple MPI ranks with this method does not distribute the memory load effectively, but does result in significant speedups.

Example

julia> using KrylovKit

julia> add = BoseFS((0,0,5,0,0));

julia> op = HubbardMom1D(add; u=6.0);

julia> pv = PDVec(add => 1.0);

julia> results = eigsolve(op, pv, 4, :SR);

julia> results[1][1:4]
4-element Vector{Float64}:
 -3.4311156892322234
  1.1821748602612363
  3.7377753753082823
  6.996390417443125

Parallel functionality

The following functions are threaded MPI-compatible:

• From Base: mapreduce and derivatives (sum, prod, reduce...), all, any,map! (on values only), +, -, *

• From LinearAlgebra: rmul!, lmul!, mul!, axpy!, axpby!, dot, norm, normalize, normalize!

• The full interface defined in VectorInterface

deposit!(w::InitiatorDVec, add, val, p_add=>p_val)

Add val into w at address add as an AbstractInitiatorValue.

deposit!(w::AbstractDVec, add, val, parent::Pair)

Add val into w at address add, taking into account initiator rules if applicable. parent contains the address => value pair from which the pair add => val was created. InitiatorDVec can intercept this and add its own functionality.

storage(dvec) -> AbstractDict

Return the raw storage associated with dvec as an AbstractDict. Used in MPI communication.

freeze(dv)

Create a "frozen" version of dv which can no longer be modified or used in the conventional manner, but supports faster dot products.

If dv is an MPIData, synchronize its contents among the ranks first.

localpart(dv) -> AbstractDVec

Get the part of dv that is located on this MPI rank. Returns dv itself for vectors that can't be MPI distributed (DVecs and InitiatorDVecs).

apply_operator!(working_memory, target, source, operator, boost=1, compress=Val(true)) ->
    stat_names, stats, working_memory, target

Perform a single matrix(/operator)-vector multiplication:

\[v^{(n + 1)} = \hat{T} v^{(n)} ,\]

where $\hat{T}$ is the operator, $v^{(n+1)}$ is the target and $v^{(n)}$ is the source. The working_memory can be used as temporary storage.

The boost argument is passed to apply_column! and increases the number of spawns performed. For the operator to be applied without compressing the vector after, set compress to Val(false).

Whether the operation is performed in a stochastic, semistochastic, or determistic way is controlled by the trait StochasticStyle(target). See StochasticStyle.

Returns the step stats generated by the StochasticStyle, the working memory and the target vector. target and working_memory may be mutated and/or swapped.

sort_into_targets!(target, source, stats) -> target, source, agg_stats

Aggregate coefficients from source to target and from stats to agg_stats according to thread- or MPI-level parallelism.

Returns the new target and source, as the sorting process may involve swapping them.

working_memory(dv::AbstractDVec)

Create a working memory instance compatible with dv. The working memory must be compatible with sort_into_targets! and apply_operator!.

walkernumber(v)

Compute the number of walkers in v. It is used for updating the shift. Overload this function for modifying population control.

In most cases walkernumber(v) is identical to norm(v, 1). For AbstractDVecs with complex coefficients it reports the one norm separately for the real and the imaginary part as a ComplexF64. See Norm1ProjectorPPop.

walkernumber(md::MPIData)

Compute the walkernumber of the distributed data on every MPI rank with MPI.Allreduce. MPI syncronizing.

dot_from_right(w, op::AbstractHamiltonian, v)

Internal function evaluates the 3-argument dot() function in order from right to left.

Abstract supertype for projectors to be used in in lieu of DVecs or Vectors in dot products. Implemented subtypes:

• UniformProjector
• NormProjector
• Norm2Projector
• Norm1ProjectorPPop

See also PostStepStrategy for use of projectors in lomc!.

Interface

Define a method for LinearAlgebra.dot(projector, v).

NormProjector() <: AbstractProjector

Results in computing the one-norm when used in dot(). E.g.

dot(NormProjector(),x)
-> norm(x,1)

NormProjector() thus represents the vector sign.(x).

See also PostStepStrategy, and AbstractProjector for use of projectors in lomc!.

Norm2Projector() <: AbstractProjector

Results in computing the two-norm when used in dot(). E.g.

dot(NormProjector(),x)
-> norm(x,2) # with type Float64

See also PostStepStrategy, and AbstractProjector for use of projectors in lomc!.

UniformProjector() <: AbstractProjector

Represents a vector with all elements 1. To be used with dot(). Minimizes memory allocations.

UniformProjector()⋅v == sum(v)
dot(UniformProjector(), LO, v) == sum(LO*v)

See also PostStepStrategy, and AbstractProjector for use of projectors in lomc!.

Norm1ProjectorPPop() <: AbstractProjector

Results in computing the one-norm per population when used in dot(). E.g.

dot(Norm1ProjectorPPop(),x)
-> norm(real.(x),1) + im*norm(imag.(x),1)

See also PostStepStrategy, and AbstractProjector for use of projectors in lomc!.

FrozenDVec

A frozen DVec(s) can't be modified or used in the conventional manner, but support faster dot products. See: freeze.

FrozenPDVec

Parallel version of FrozenDVec. See: freeze, PDVec.

InitiatorRule{V}

Abstract type for defining initiator rules for InitiatorDVec. Concrete implementations:

• Initiator
• SimpleInitiator
• CoherentInitiator
• NonInitiator

Extended Help

InitiatorRules define how to store and retrieve data from associated AbstractInitiatorValues. When defining a new InitiatorRule, also define the following:

• initiator_valtype
• from_initiator_value
• to_initiator_value

abstract type AbstractInitiatorValue{V}

A value equipped with additional information that enables a variation of the initiator approximation. To be used with PDVec, InitiatorDVec and InitiatorRules.

Must define:

• Base.zero, Base.:+, Base.:-, Base.:*
• from_initiator_value and to_initiator_value

InitiatorValue{V}(; safe::V, unsafe::V, initiator::V) where V

Composite "walker" with three fields. For use with InitiatorDVecs.

initiator_valtype(rule::InitiatorRule, T)

Return the AbstractInitiatorValue{T} that is employed by the rule.

to_initiator_value(::InitiatorRule, k::K, v::V, parent)

Convert v to an AbstractInitiatorValue, taking the initiator rule and the parent that spawned it into account.

from_initiator_value(i::InitiatorRule, v::AbstractInitiatorValue)

Convert the AbstractInitiatorValue v into a scalar value according to the InitiatorRule i.

Initiator(threshold = 1.0) <: InitiatorRule

Initiator rule to be passed to PDVec or InitiatorDVec. An initiator is a configuration add with a coefficient with magnitude abs(v[add]) > threshold. The threshold can be passed as a keyword argument. Rules:

• Initiators can spawn anywhere.
• Non-initiators can spawn to initiators.

See InitiatorRule.

SimpleInitiator(threshold = 1.0) <: InitiatorRule

Initiator rule to be passed to PDVec or InitiatorDVec. An initiator is a configuration add with a coefficient with magnitude abs(v[add]) > threshold. The threshold can be passed as a keyword argument. Rules:

• Initiators can spawn anywhere.
• Non-initiators cannot spawn.

See InitiatorRule.

CoherentInitiator(threshold = 1.0) <: InitiatorRule

Initiator rule to be passed to PDVec or InitiatorDVec. An initiator is a configuration add with a coefficient with magnitude abs(v[add]) > threshold. The threshold can be passed as a keyword argument. Rules:

• Initiators can spawn anywhere.
• Non-initiators can spawn to initiators.
• Multiple non-initiators can spawn to a single non-initiator if their contributions add up to a value greater than the initiator threshold.

See InitiatorRule.

NonInitiator() <: InitiatorRule

Initiator rule that disables the approximation. This is the default setting for PDVec.

See InitiatorRule.

NonInitiatorValue{V}

Value that does not contain any additional information - used with NonInitiator, the default initiator rule for PDVec.

MainSegmentIterator{W,D} <: AbstractVector{D}

Iterates the main segments of a specified rank. See remote_segments and local_segments.

PDWorkingMemory(t::PDVec)

The working memory that handles threading and MPI distribution for operations that involve operators, such as FCIQMC propagation, operator-vector multiplication and three-way dot products with PDVecs.

The working memory is structured in a series of columns, where each has a number of segments (see PDVec) equal to the number of segments across all MPI ranks. The purpose of this organisation is to allow spawning in parallel without using locks or atomic operations.

The steps performed on a PDWorkingMemory during a typical operation are perform_spawns!, collect_local!, synchronize_remote!, and move_and_compress!.

When used with three-argument dot products, a full copy of the left-hand side vector is materialized in the first column of the working memory on all ranks.

PDWorkingMemoryColumn

A column in PDWorkingMemory. Supports deposit! and StochasticStyle and acts as a target for spawning.

collect_local!(w::PDWorkingMemory)

Collect each row in w into its main segment. This step must be performed before using local_segments or remote_segments to move the values elsewhere.

See PDWorkingMemory.

local_segments(w::PDWorkingMemory)

Returns iterator over the main segments on the current rank. Iterates Dicts.

See PDWorkingMemory.

main_column(::PDWorkingMemory) -> PDVec

Return the "main" column of the working memory wrapped in a PDVec.

See PDWorkingMemory.

move_and_compress!(dst::PDVec, src::PDWorkingMemory)
move_and_compress!(::CompressionStrategy, dst::PDVec, src::PDWorkingMemory)

Move the values in src to dst, compressing the according to the CompressionStrategy on the way. This step can only be performed after collect_local! and synchronize_remote!.

See PDWorkingMemory.

num_columns(w::PDWorkingMemory) -> Int

Number of columns in the working memory. The number of rows is equal to the number of segments in the local rank.

num_rows(w::PDWorkingMemory) -> Int

Number of rows in the working memory. The number of rows is equal to the number of segments accross all ranks.

perform_spawns!(w::PDWorkingMemory, t::PDVec, ham, boost)

Perform spawns from t through ham to w.

See PDVec and PDWorkingMemory.

remote_segments(w::PDWorkingMemory, rank_id)

Returns iterator over the main segments that belong to rank rank_id. Iterates Dicts.

See PDWorkingMemory.

synchronize_remote!(w::PDWorkingMemory)

Synchronize non-local segments across MPI. Controlled by the Communicator. This can only be perfomed after collect_local!.

See PDWorkingMemory.

abstract type Communicator

Communicators are used to handle MPI communication when using PDVecs. Currently, two implementations are provided, NotDistributed, and PointToPoint. The communicator is picked automatically according to the number of MPI ranks available.

When implementing a communicator, use local_segments and remote_segments.

Interface

• synchronize_remote!
• mpi_rank
• mpi_size
• mpi_comm

Optional interface

• is_distributed: defaults to returning true.
• merge_remote_reductions: defaults to using MPI.Allreduce.
• total_num_segments: defaults to n * mpi_size.
• target_segment: defaults to selecting using fastrange to pick the segment.

LocalPart <: Communicator

When localpart is used, the vector's Communicator is replaced with this. This allows iteration and local reductions.

NotDistributed <: Communicator

This Communicator is used when MPI is not available.

PointToPoint <: Communicator

Communicator that uses circular communication using MPI.Isend and MPI.Recv!.

SegmentedBuffer

Multiple vectors stored in a simple buffer with MPI communication.

See replace_collections!, mpi_send, mpi_recv_any!.

copy_to_local!([::Communicator,] w::PDWorkingMemory, t::PDVec) -> PDVec

Copy pairs in t from all ranks and return them as (possibly) new PDVec, possibly using the PDWorkingMemory as temporary storage.

is_distributed(::Communicator)

Return true if communicator operates over MPI.

merge_remote_reductions(c::Communicator, op, x)

Merge the results of reductions over MPI. By default, it uses MPI.Allreduce.

mpi_comm(::Communicator) -> MPI.Comm

Return the MPI.Comm that the Communicator operates on.

mpi_rank(::Communicator) -> Int

Return the MPI rank of the Communicator.

mpi_recv_any!(buf::SegmentedBuffer, comm) -> Int

Find a source that is ready to send a buffer and receive from it. Return the rank ID of the sender.

mpi_send(buf::SegmentedBuffer, dest, comm)

Send the buffers to dest.

mpi_size(::Communicator) -> Int

Return the total number of MPI ranks in the Communicator.

replace_collections!(buf::SegmentedBuffer, iters)

Insert collections in iters into buffers.

synchronize_remote!([::Communicator,] ::PDWorkingMemory)

Copy pairs from remote ranks to the local part of the PDWorkingMemory.

target_segment(c::Communicator, k, num_segments) -> target, is_local

This function is used to determine where in the PDVec a key should be stored.

If the key is local (stored on the same MPI rank), return its segment index and true. If the key is non-local, return any value and false.

total_num_segments(c::Communicator, n) -> Int

Return the total number of segments, including the remote ones, where n is number of local segments.