# Quickstart¶

The primary functionality of the library is a highly-configurable, performant
implementation of the (Approximate)
Minimum Degree reordering algorithm [AmestoyEtAl-1996].
An implementation of an alternative storage mechanism to `std::vector<T>`

which avoids default initialization, `quotient::Buffer<T>`

, is also
provided.

This brief quickstart guide walks through building the examples and tests using the meson build system and provides short overviews of the major functionality.

## Building the examples and tests¶

While quotient is a header-only library, there are a number of configuration options which are handled through preprocessor directives and compiler/linker options determined during a configuration stage. Quotient uses meson, a modern alternative to CMake, for this configuration.

One might start with a debug build (the default `buildtype`

in
meson). Assuming that the
Ninja build system was installed alongside
meson (it typically is), one can configure and build catamari with its default
options via:

```
mkdir build-debug/
meson build-debug
cd build-debug
ninja
```

A release version can be built by specifying the `buildtype`

option as
`release`

:

```
mkdir build-release/
meson build-release -Dbuild-type=release
cd build-release
ninja
```

By default, quotient is configured with `quotient::Int`

equal to a
64-bit signed integer. But the library can be configured with 32-bit integer
support via the `-Duse_64bit=false`

option.

In any build configuration, the library’s unit tests can be run via:

```
ninja test
```

## Using `quotient::Buffer<T>`

instead of `std::vector<T>`

¶

A well-known issue with `std::vector<T>`

is that it cannot be readily used
to allocate data without initializing each entry. In the case of
catamari’s multithreaded sparse-direct
solver, sequential default initialization overhead was seen to be a significant
bottleneck when running on 16 cores. Due to the interdependence of quotient and
catamari, quotient performs its Minimum Degree reordering on top of a custom
`quotient::Buffer<T>`

template class as an alternative buffer allocation
mechanism.

Both `std::vector<T>`

and `quotient::Buffer<T>`

have the same
`operator[]`

entry access semantics.

The function `quotient::Buffer<T>::Resize(std::size_t)`

is
an alternative to `std::vector<T>::resize(std::size_t)`

which does not
default-initialize members. Likewise,
`quotient::Buffer<T>::Resize(std::size_t, const T& value)`

is an
analogue for `std::vector<T>::resize(std::size_t, const T& value)`

, but
it differs in that it will ensure that **all** members of the result are equal
to the specified value (not just newly allocated ones).

Lastly, the underlying data pointer can be accessed via
`quotient::Buffer<T>::Data()`

instead of
`std::vector<T>::data()`

(the `begin()`

and `end()`

member
functions exist so that range-based for loops function over
`quotient::Buffer<T>`

).

A simple example combining all of these features is:

```
#include <iostream>
#include "quotient.hpp"
const std::size_t num_entries = 5;
quotient::Buffer<float> entries;
entries.Resize(num_entries);
// The five entries are not yet initialized.
// Initialize the i'th entry as i^2.
for (std::size_t i = 0; i < num_entries; ++i) {
entries[i] = i * i;
}
// Print the entries.
std::cout << "entries: ";
for (const float& entry : entries) {
std::cout << entry << " ";
}
std::cout << std::endl;
// Double the length of the buffer and zero-initialize.
entries.Resize(2 * num_entries, 0.f);
// Extract a mutable pointer to the entries.
float* entries_ptr = entries.Data();
```

## Manipulating graphs with `CoordinateGraph`

¶

The current user-level interface for manipulating graphs is via the
coordinate-format class `quotient::CoordinateGraph`

. Its primary
underlying data is a lexicographically sorted
`quotient::Buffer<quotient::GraphEdge>`

and an associated
`quotient::Buffer<Int>`

of row offsets (which serve the
same role as in a Compressed Sparse Row (CSR) format). Thus, this storage
scheme is a superset of the CSR format that explicitly stores both row and
column indices for each entry.

The `quotient::GraphEdge`

struct is a typedef of a
`std::pair<quotient::Int, quotient::Int>`

containing the row and column
index.

The class is designed so that the sorting and offset computation overhead can be amortized over batches of edge insertions and removals.

For example, the code block:

```
#include "quotient.hpp"
quotient::CoordinateGraph graph;
graph.Resize(5);
graph.ReserveEdgeAdditions(6);
graph.QueueEdgeAddition(3, 4);
graph.QueueEdgeAddition(2, 3);
graph.QueueEdgeAddition(2, 0);
graph.QueueEdgeAddition(4, 2);
graph.QueueEdgeAddition(4, 4);
graph.QueueEdgeAddition(3, 2);
graph.FlushEdgeQueues();
const quotient::Buffer<quotient::GraphEdge>& edges = graph.Edges();
```

would return a reference to the underlying
`quotient::Buffer<quotient::GraphEdge>`

of `graph`

,
which should contain the edge sequence:

`(2, 0), (2, 3), (3, 2), (3, 4), (4, 2), (4, 4)`

.

Similarly, subsequently running the code block:

```
graph.ReserveEdgeRemovals(2);
graph.QueueEdgeRemoval(2, 3);
graph.QueueEdgeRemoval(0, 4);
graph.FlushEdgeQueues();
```

would modify the Buffer underlying the `edges`

reference to now
contain the edge sequence:

`(2, 0), (3, 2), (3, 4), (4, 2), (4, 4)`

.

## (Approximate) Minimum Degree reorderings¶

In the simplest case (using default options), an (Approximate) Minimum Degree
[AmestoyEtAl-1996] analysis can be run on a symmetric graph stored in a
`quotient::CoordinateGraph`

via:

```
#include "quotient.hpp"
quotient::MinimumDegreeControl control;
quotient::QuotientGraph quotient_graph(*graph, control);
const quotient::MinimumDegreeResult analysis =
quotient::MinimumDegree("ient_graph);
```

The implied permutation (and its inverse) which produces the (Approximate) Minimum Degree reordering can then be extracted via:

```
quotient::Buffer<quotient::Int> permutation, inverse_permutation;
quotient_graph.ComputePostorder(&inverse_permutation);
quotient::InvertPermutation(inverse_permutation, &permutation);
```

If the sizes of the contiguous (in the permuted ordering) supernodes are desired, they can be extracted using the newly formed permutation via:

```
quotient::Buffer<quotient::Int> supernode_sizes;
quotient_graph.PermutedSupernodeSizes(inverse_permutation, &supernode_sizes);
```

The map from each reordered index into the index of its containing supernode can be formed via:

```
quotient::Buffer<quotient::Int> member_to_supernode;
quotient_graph.PermutedMemberToSupernode(inverse_permutation,
&member_to_supernode);
```

Said map can then be used to generate the up-links of the supernodal assembly forest via:

```
quotient::Buffer<quotient::Int> parents;
quotient_graph.PermutedAssemblyParents(permutation, member_to_supernode,
&parents);
```

Said graph can be easily visualized by writing it out to a DOT file:

```
quotient::ForestToDot("your_filename.gv", parents);
```

An example exercising all of these routines is available in example/matrix_market_minimum_degree.cc.

## Testing performance¶

The default is for Quotient to use 64-bit integers, but there is a noticeable performance difference relative to 32-bit integers due to the work primarily consisting of memory-bound index manipulation. As mentioned above, a release-mode 64-bit version can be built with:

```
mkdir build-release-64/
meson build-release-64 --buildtype=release
cd build-release-64
ninja
```

whereas a 32-bit, release-mode version can be built with:

```
mkdir build-release-32/
meson build-release-32 --buildtype=release
cd build-release-32
meson configure -Duse_64bit=false
ninja
```

One could then download and unpack, for example, the
LHR34
matrix market description into `$`

and then test performance
with and without aggressive absorption using:*HOME*/Data/lhr34.mtx

```
time ./matrix_market_minimum_degree --filename="${HOME}/Data/lhr34.mtx" --print_progress=true --aggressive_absorption=true
time ./matrix_market_minimum_degree --filename="${HOME}/Data/lhr34.mtx" --print_progress=true --aggressive_absorption=false
```

## References¶

[AmestoyEtAl-1996] | (1, 2) Patrick R. Amestoy, Timothy A. Davis, and Iain S. Duff, An Approximate Minimum Degree Reordering Algorithm, SIAM J. Matrix Analysis & Applic., 17 (4), pp. 886–905, 1996. DOI: https://doi.org/10.1137/S0895479894278952 |