Matrix Development API

Similar matrices 

oars.matrices.getMinSpectralDifference(n, **kwargs)[source]

Find convergence matrix W and consensus matrix Z that minimize \(\|Z-W\|\)

Parameters:

n (int) – number of resolvents
kwargs –
keyword arguments
- fixed_Z (dict): dictionary of fixed Z values with keys as (i,j) tuples
- fixed_W (dict): dictionary of fixed W values with keys as (i,j) tuples
- c (float): connectivity parameter
- eps (float): allowable deviation from 2 in Z diagonal
- gamma (float): scaling parameter for Z
- adj (bool): whether to use the edge adjacency formulation

Returns:

Z (ndarray) – n x n consensus matrix
W (ndarray) – n x n resolvent matrix
alpha (float) – scaling factor for resolvent if eps is nonzero

Examples

>>> from oars.matrices import getMinSpectralDifference
>>> Z, W = getMinSpectralDifference(4, fixed_W={(3, 0): 0}, fixed_Z={(1, 0): 0})
>>> print(Z)
[[ 2.    -0.    -1.645 -0.355]
[-0.     2.    -0.355 -1.645]
[-1.645 -0.355  2.    -0.   ]
[-0.355 -1.645 -0.     2.   ]]
>>> print(W)
[[ 1.645 -0.17  -1.475 -0.   ]
[-0.17   1.918 -0.273 -1.475]
[-1.475 -0.273  1.918 -0.17 ]
[-0.    -1.475 -0.17   1.645]]

Minimum Second-Largest Eigenvalue 

oars.matrices.getMinSLEM(n, vz=1.0, vw=1.0, **kwargs)[source]

Find convergence matrix W and consensus matrix Z that minimize the sum of the SLEM values for W and Z

Parameters:

n (int) – number of resolvents
vz (float) – weight for Z SLEM value
vw (float) – weight for W SLEM value
**kwargs –
keyword arguments for verbosity and cvxpy solver
- fixed_Z (dict): dictionary of fixed Z values with keys as (i,j) tuples
- fixed_W (dict): dictionary of fixed W values with keys as (i,j) tuples
- c (float): connectivity parameter
- eps (float): allowable deviation from 2 in Z diagonal
- gamma (float): scaling parameter for Z
- adj (bool): whether to use the edge adjacency formulation

Returns:

Z (ndarray) – n x n resolvent matrix
W (ndarray) – n x n consensus matrix
alpha (float) – scaling factor for resolvent if eps is nonzero

Examples

>>> from oars.matrices import getMinSLEM
>>> Z, W = getMinSLEM(4, fixed_W={(3, 0): 0}, fixed_Z={(1, 0): 0})
>>> print(Z)
[[ 2.    -0.    -1.333 -0.667]
[-0.     2.    -0.667 -1.333]
[-1.333 -0.667  2.    -0.   ]
[-0.667 -1.333 -0.     2.   ]]
>>> print(W)
[[ 1.333 -0.667 -0.667  0.   ]
[-0.667  1.333 -0.    -0.667]
[-0.667 -0.     1.333 -0.667]
[ 0.    -0.667 -0.667  1.333]]

Minimum Total Effective Resistance 

oars.matrices.getMinResist(n, vz=1.0, vw=1.0, **kwargs)[source]

Find convergence matrix W and consensus matrix Z that minimize the sum of the total effective resistances for W and Z

Parameters:

n (int) – number of resolvents
fixed_Z (dict) – dictionary of fixed Z values with keys as (i,j) tuples
fixed_W (dict) – dictionary of fixed W values with keys as (i,j) tuples
vz (float) – weight for Z TER value
vw (float) – weight for W TER value
**kwargs –
keyword arguments for verbosity and cvxpy solver
- c (float): connectivity parameter
- eps (float): allowable deviation from 2 in Z diagonal
- gamma (float): scaling parameter for Z
- adj (bool): whether to use the edge adjacency formulation

Returns:

Z (ndarray) – n x n resolvent matrix
W (ndarray) – n x n consensus matrix
alpha – scaling factor for resolvent if eps is nonzero

Examples

>>> from oars.matrices import getMinResist
>>> Z, W = getMinResist(4, fixed_W={(3, 0): 0}, fixed_Z={(1, 0): 0}, gamma=1.5)
>>> print(Z)
[[ 2.     0.    -1.174 -0.826]
[ 0.     2.    -0.826 -1.174]
[-1.174 -0.826  2.     0.   ]
[-0.826 -1.174  0.     2.   ]]
>>> print(W)
[[ 1.76  -0.704 -1.056  0.   ]
[-0.704  2.6   -0.84  -1.056]
[-1.056 -0.84   2.6   -0.704]
[ 0.    -1.056 -0.704  1.76 ]]

Maximum Algebraic Connectivity 

oars.matrices.getMaxConnectivity(n, vz=1.0, vw=1.0, **kwargs)[source]

Find convergence matrix W and consensus matrix Z that maximize the sum of the algebraic connectivity for W and Z

Parameters:

n (int) – number of resolvents
fixed_Z (dict) – dictionary of fixed Z values with keys as (i,j) tuples
fixed_W (dict) – dictionary of fixed W values with keys as (i,j) tuples
vz (float) – weight for Z Fiedler value
vw (float) – weight for W Fiedler value
**kwargs –
keyword arguments for verbosity and cvxpy solver
- c (float): connectivity parameter
- eps (float): allowable deviation from 2 in Z diagonal
- gamma (float): scaling parameter for Z
- adj (bool): whether to use the edge adjacency formulation

Returns:

Z (ndarray) – n x n resolvent matrix
W (ndarray) – n x n consensus matrix
alpha (float) – scaling factor for resolvent if eps is nonzero

Examples

>>> from oars.matrices import getMaxConnectivity
>>> Z, W = getMaxConnectivity(4, fixed_W={(3, 0): 0}, fixed_Z={(1, 0): 0})
>>> print(Z)
[[ 2.  0. -1. -1.]
[ 0.  2. -1. -1.]
[-1. -1.  2.  0.]
[-1. -1.  0.  2.]]
>>> print(W)
[[ 1.    -0.5   -0.5   -0.   ]
[-0.5    1.459 -0.459 -0.5  ]
[-0.5   -0.459  1.459 -0.5  ]
[-0.    -0.5   -0.5    1.   ]]

Block Matrices 

oars.matrices.getBlockMin(n, m, builder=<function getMinSpectralDifference>, **kwargs)[source]

Get the d-Block design with block size m (or list of block sizes with length d). If m is an integer, \(d = \text{ceil}(n/m)\). Uses a provided builder function to specify the objective function and any other constraints in addition to the d-Block constraints. The default builder is getMinSpectralDifference.

Parameters:

n (int) – number of resolvents
m (int or list of ints) – block size, either an integer or a list of integers
builder (function) – builder function that takes n (int), fixed_Z (dict), fixed_W (dict) and kwargs and returns Z, W, alpha
kwargs –
keyword arguments for the builder function
- c (float): connectivity parameter
- eps (float): allowable deviation from 2 in Z diagonal
- gamma (float): scaling parameter for Z
- adj (bool): whether to use the edge adjacency formulation

Returns:

Z (ndarray) – (n,n) resolvent matrix
W (ndarray) – (n,n) consensus matrix
alpha (float) – scaling factor for resolvent if eps is nonzero

Examples

>>> from oars.matrices import getBlockMin, getMinResist
>>> Z, W = getBlockMin(6, 2, builder=getMinResist)
>>> print(Z)
[[ 2.   0.  -0.5 -0.5 -0.5 -0.5]
[ 0.   2.  -0.5 -0.5 -0.5 -0.5]
[-0.5 -0.5  2.   0.  -0.5 -0.5]
[-0.5 -0.5  0.   2.  -0.5 -0.5]
[-0.5 -0.5 -0.5 -0.5  2.   0. ]
[-0.5 -0.5 -0.5 -0.5  0.   2. ]]
>>> print(W)
[[ 1.5 -0.5 -0.5 -0.5  0.   0. ]
[-0.5  1.5 -0.5 -0.5  0.   0. ]
[-0.5 -0.5  2.   0.  -0.5 -0.5]
[-0.5 -0.5  0.   2.  -0.5 -0.5]
[ 0.   0.  -0.5 -0.5  1.5 -0.5]
[ 0.   0.  -0.5 -0.5 -0.5  1.5]]

Core 

oars.matrices.getCore(n, fixed_Z={}, fixed_W={}, c=None, eps=0.0, gamma=1.0, adj=False, **kwargs)[source]

Get core variables and constraints for the algorithm design SDP

\(W \mathbb{1} = 0\)

\(Z \mathbb{1} = 0\)

\(\lambda_{1}(W) + \lambda_{2}(W) \geq c\)

\(Z - W \succeq 0\)

\(\mathrm{diag}(Z) = Z_{11}\mathbb{1}\)

\(2 - \varepsilon \leq Z_{11} \leq 2 + \varepsilon\)

Parameters:

n (int) – number of nodes
fixed_Z (dict) – dictionary of fixed Z values with keys as (i,j) tuples
fixed_W (dict) – dictionary of fixed W values with keys as (i,j) tuples
c (float) – connectivity parameter (default 2*(1-cos(pi/n)))
eps (float) – epsilon for Z[0,0] = 2 + eps constraint
gamma (float) – scaling parameter for Z
adj (bool) – whether to use the edge adjacency formulation
kwargs – additional keyword arguments for the algorithm

Returns:

Z (ndarray) – n x n cvxpy decision variable matrix for Z
W (ndarray) – n x n cvxpy decision variable matrix for W
cons (list) – list of cvxpy constraints

Examples

>>> import cvxpy as cvx
>>> from oars.matrices import getCore
>>> Z, W, cons = getCore(4, fixed_W={(3, 0): 0})
>>> obj = cvx.Minimize(cvx.norm(Z-W, 'fro'))
>>> prob = cvx.Problem(obj, cons)
>>> prob.solve()
>>> print(Z.value)
[[ 2. -1. -1. -0.]
[-1.  2. -0. -1.]
[-1. -0.  2. -1.]
[-0. -1. -1.  2.]]
>>> print(W.value)
[[ 2. -1. -1. -0.]
[-1.  2. -0. -1.]
[-1. -0.  2. -1.]
[-0. -1. -1.  2.]]

Reduced Matrix: Cholesky 

oars.matrices.getMfromWCholesky(W)[source]

Reconstruct M from W via the cholesky decomposition, as described in the paper.

Parameters:: W (ndarray) – n x n symmetric psd numpy array w/ Null(W) = 1
Returns:: M (ndarray) – (n-1) x n array such that M.T @ M = W

Examples

>>> from oars.matrices import getMfromWCholesky, getTwoBlockSimilar
>>> Z, W = getTwoBlockSimilar(4)
>>> M = getMfromWCholesky(W)
>>> print(M)
[[-1.     1.     0.     0.   ]
[-0.707 -0.707  1.414  0.   ]
[-0.707 -0.707  0.     1.414]]

Reduced Matrix: Eigenvalue Decomposition 

oars.matrices.getMfromWEigen(W)[source]

Reconstruct M from W via the eigenvalue decomposition, as described in the paper.

Parameters:: W (ndarray) – n x n symmetric psd numpy array w/ Null(W) = 1
Returns:: M (ndarray) – (n-1) x n array such that M.T @ M = W

Examples

>>> from oars.matrices import getMfromWEigen, getTwoBlockSimilar
>>> Z, W = getTwoBlockSimilar(4)
>>> M = getMfromWEigen(W)
>>> print(M)
[[-1.  1. -0. -0.]
[ 0.  0. -1.  1.]
[-1. -1.  1.  1.]]

Reduced Matrix: Incidence Matrix 

oars.matrices.getIncidence(W)[source]

Convert a Stieltjes graph Laplacian W to an incidence matrix

Parameters:: W (ndarray) – n x n numpy array of graph Laplacian with only negative off-diagonal entries
Returns:: M (ndarray) – m x n numpy array of incidence matrix where m is the number of edges

Examples

>>> from oars.matrices import getIncidence, getTwoBlockSimilar
>>> Z, W = getTwoBlockSimilar(4)
>>> M = getIncidence(W)
>>> print(M)
[[-1.  0.  1.  0.]
[ 0. -1.  1.  0.]
[-1.  0.  0.  1.]
[ 0. -1.  0.  1.]]

Block Matrix Constraints 

oars.matrices.getBlockFixed(n, m)[source]

Get prohibited values for block size(s) m

Parameters:

n (int) – number of resolvents
m (int or list of ints) – block size, either an integer or a list of integers

Returns:

Z_fixed (dict) – dictionary of fixed Z values with keys as (i,j) tuples
W_fixed (dict) – dictionary of fixed W values with keys as (i,j) tuples

Examples

>>> from oars.matrices import getBlockFixed
>>> Z_fixed, W_fixed = getBlockFixed(4, 2)
>>> print(Z_fixed)
{(1, 0): 0, (3, 2): 0}
>>> print(W_fixed)
{}

Fully Connected Design 

oars.matrices.getFull(n)[source]

Return Z, W for a fully connected graph with n nodes and weight 2 evenly distributed among all edges

Parameters:

n (int) – number of resolvents

Returns:

Z (ndarray) – n x n numpy array for the graph Laplacian of a fully connected weighted graph with n nodes where the weights are evenly distributed among all edges and the weighted degree of each node is 2
W (ndarray) – n x n numpy array which is the same as Z

Malitsky-Tam Design 

oars.matrices.getMT(n)[source]

Get Malitsky-Tam values for Z and W

Parameters:

n (int) – number of resolvents

Returns:

Z (ndarray) – Z matrix n x n numpy array
W (ndarray) – W matrix n x n numpy array

Ryu-Tam Design 

oars.matrices.getRyu(n)[source]

Get Tam’s extension of the Ryu algorithm values for Z and W

Parameters:

n (int) – number of resolvents

Returns:

Z (ndarray) – Z matrix n x n numpy array
W (ndarray) – W matrix n x n numpy array

Minimum Iteration Time 

oars.matrices.getMinIteration(n, builder=<function getMinSpectralDifference>, **kwargs)[source]

Get the minimum iteration time algorithm for a given objective function and optional keyword arguments

Parameters:

n (int) – number of resolvents
builder (function) – builder function for desired objective with signature builder(n, fixed_Z, fixed_W, **kwargs)
kwargs –
additional keyword arguments for the algorithm
- t (list): list of resolvent compute times
- l (ndarray): n x n array of communication times
- fixed_X (dict): dictionary of fixed communication relationships for Z
- fixed_Y (dict): dictionary of fixed communication relationships for W
- r (int): number of iterations to optimize over
- minZ (int): the number of edges required for each resolvent in Z
- minW (int): the number of edges required for each resolvent in W
- Zedges (int): the minimum number of edges in Z as a whole
- Wedges (int): the minimum number of edges in W as a whole
- minfixed (bool, ‘Z’, or ‘W’): whether to include the number of edges in the objective with weight weight
- weight (float): the coefficient for the weight on the sum of edges in the objective
- solver_name (str): the name of the solver to use

Returns:

Z (ndarray) – Z matrix n x n numpy array
W (ndarray) – W matrix n x n numpy array
alpha (float) – the proximal scaling parameter if eps != 0

Two Block Design - Similar Matrices 

oars.matrices.getTwoBlockSimilar(n)[source]

Get two block similar matrices for Z and W Each has twos on the diagonal and -4/n in the off-diagonal n//2 x n//2 blocks

Parameters:

n (int) – number of resolvents

Returns:

Z (ndarray) – Z matrix n x n numpy array
W (ndarray) – W matrix n x n numpy array

Two Block Design - SLEM 

oars.matrices.getTwoBlockSLEM(n)[source]

Get two block matrices for Z and W Z has twos on the diagonal and 4/(n-1) in the off-diagonal n//2 x n//2 blocks W is \(2I - \frac{2}{n}\mathbf{1}\mathbf{1}^T\)

Parameters:

n (int) – number of resolvents

Returns:

Z (ndarray) – Z matrix n x n numpy array
W (ndarray) – W matrix n x n numpy array

Three Block Design - Similar Matrices 

oars.matrices.getThreeBlockSimilar(n)[source]: Get three block similar matrices for Z and W where the blocks are n//4, n//2, n-(n//4 + n//2) in size