Arrays

Arrays

This module provides machinery for vectors and matrices.

argmaxabs(x::AbstractArray)

Return the index with the absolute-wise maximum entry.

Input

• x – array

Output

The index i such that |x[i]| >= |x[j]| for all j.

cross_product(M::AbstractMatrix{N}) where {N<:Real}

Compute the high-dimensional cross product of $n-1$ $n$-dimensional vectors.

Input

• M – $n × n - 1$-dimensional matrix

Output

A vector.

Algorithm

The cross product is defined as follows:

\[\left[ \dots, (-1)^{n+1} \det(M^{[i]}), \dots \right]^T\]

where $M^{[i]}$ is defined as $M$ with the $i$-th row removed. See Althoff, Stursberg, Buss: Computing Reachable Sets of Hybrid Systems Using a Combination of Zonotopes and Polytopes. 2009.

distance(x::AbstractVector{N}, y::AbstractVector{N}; [p]::Real=N(2)) where {N}

Compute the distance between two vectors with respect to the given p-norm, computed as

\[ \|x - y\|_p = \left( \sum_{i=1}^n | x_i - y_i |^p \right)^{1/p}\]

Input

• x – vector
• y – vector
• p – (optional, default: 2.0) the p-norm used; p = 2.0 corresponds to the usual Euclidean norm

Output

A scalar representing $‖ x - y ‖_p$.

dot_zero(x::AbstractVector{N}, y::AbstractVector{N}) where{N<:Real}

Dot product with preference for zero value in the presence of infinity values.

Input

• x – first vector
• y – second vector

Output

The dot product of x and y, but with the rule that 0 * Inf == 0.

extend(M::AbstractMatrix; check_rank=true)

Return an invertible extension of M whose first n columns span the column space of M, assuming that size(M) = (m, n), m > n and the rank of M is n.

Input

• M – rectangular m × n matrix with m > n and full rank (i.e. its rank is n)
• check_rank – (optional, default: true) if true, check the rank assumption, otherwise do not perform this check

Output

The tuple (Mext, inv_Mext), where Mext is a square m × m invertible matrix that extends M, i.e. in the sense that Mext = [M | Q2], and the rank of Mext is m. Here, inv_Mext is the inverse of Mext.

Algorithm

First we compute the QR decomposition of M to extract a suitable subspace of column vectors (Q2) that are orthogonal to the column span of M. Then we observe that the inverse of the extended matrix Mext = [M | Q2] is [R⁻¹Qᵀ; Q2ᵀ].

extend_with_zeros(x::AbstractVector, indices::AbstractVector{<:Int})

Extend a vector with zeros in the given dimensions.

Input

• x – vector
• indices – indices to extend, from the interval 1:(length(x) + length(indices))

Output

A new vector.

Notes

The indices in the extension list are interpreted on the output vector. This is best understood with an example. Let x = [1, 2, 3] and indices = [3, 5]. Then the output vector is y = [1, 2, 0, 3, 0]. Indeed, y[3] == y[5] == 0.

hasfullrowrank(M::AbstractMatrix)

Check whether a matrix has full row rank.

Input

• M – matrix

Output

true iff the matrix has full row rank.

inner(x::AbstractVector{N}, A::AbstractMatrix{N}, y::AbstractVector{N}
     ) where {N}

Compute the inner product $xᵀ A y$.

Input

• x – vector on the left
• A – matrix
• y – vector on the right

Output

The (scalar) result of the multiplication.

is_cyclic_permutation(candidate::AbstractVector, paragon::AbstractVector)

Checks if the elements in candidate are a cyclic permutation of the elements in paragon.

Input

• candidate – candidate vector
• paragon – paragon vector

Output

A boolean indicating if the elements of candidate are in the same order as in paragon or any of its cyclic permutations.

is_right_turn([O::AbstractVector{<:Real}=[0, 0]], u::AbstractVector{<:Real},
              v::AbstractVector{<:Real})

Determine whether the acute angle defined by three 2D points O, u, v in the plane is a right turn (< 180° counter-clockwise) with respect to the center O. Determine if the acute angle defined by two 2D vectors is a right turn (< 180° counter-clockwise) with respect to the center O.

Input

• O – (optional; default: [0, 0]) 2D center point
• u – first 2D direction
• v – second 2D direction

Output

true iff the vectors constitute a right turn.

isabove(u::AbstractVector, v1::AbstractVector, v2::AbstractVector)

Checks whether the difference v1 - v2 points toward the given direction u.

Input

• u – direction
• v1 – first vector
• v2 – second vector

Output

A Boolean indicating whether the difference of the given vectors points toward the given direction.

Algorithm

The result is equivalent to dot(u, v1 - v2) > 0, but the implementation avoids the allocation of the difference vector.

isinvertible(M::Matrix; [cond_tol]::Number=1.0e6)

A sufficient check of a matrix being invertible (or nonsingular).

Input

• M – matrix
• cond_tol – (optional, default: 1.0e6) tolerance of matrix condition

Output

If the result is true, M is invertible. If the result is false, the matrix is non-square or not well-conditioned.

Algorithm

We check whether the matrix is square and well-conditioned (via iswellconditioned).

ismultiple(u::AbstractVector{<:Real}, v::AbstractVector{<:Real})

Check whether two vectors are linearly dependent.

Input

• u – first vector
• v – second vector

Output

(true, k) iff the vectors are identical up to a scaling factor k ≠ 0 such that u = k * v, and (false, 0) otherwise.

Examples

julia> ismultiple([1, 2, 3], [2, 4, 6])
(true, 0.5)

julia> ismultiple([1, 2, 3], [3, 2, 1])
(false, 0)

julia> ismultiple([1, 2, 3], [-1, -2, -3])
(true, -1.0)

ispermutation(u::AbstractVector{T}, v::AbstractVector) where {T}

Check that two vectors contain the same elements up to reordering.

Input

• u – first vector
• v – second vector

Output

true iff the vectors are identical up to reordering.

Examples

julia> ispermutation([1, 2, 2], [2, 2, 1])
true

julia> ispermutation([1, 2, 2], [1, 1, 2])
false

Notes

Containment check is performed using Comparison._in(e, v), so in the case of floating point numbers, the precision to which the check is made is determined by the type of elements in v. See _in and _isapprox for more information.

Note that approximate equality is not an equivalence relation. Hence the result may depend on the order of the elements.

issquare(M::AbstractMatrix)

Check whether a matrix is square.

Input

• M – matrix

Output

true iff the matrix is square.

iswellconditioned(M::Matrix; [cond_tol]::Number=1.0e6)

A check of a matrix being sufficiently well-conditioned.

Input

• M – matrix
• cond_tol – (optional, default: 1.0e6) tolerance of matrix condition

Output

true iff M is well-conditioned subject to the cond_tol parameter.

Algorithm

We check whether the matrix condition number cond(M) is below the prescribed tolerance cond_tol.

matrix_type(T)

Return a corresponding matrix type with respect to type T.

Input

• T – vector or matrix type

Output

A matrix type that corresponds in some sense (see Notes below) to T.

Notes

• If T is a sparse vector or a sparse matrix, the corresponding type is also a sparse matrix.
• If T is a regular vector (i.e. Vector) or a regular matrix (i.e. Matrix), the corresponding type is also a regular matrix.
• Otherwise, the corresponding type is a regular matrix.

nonzero_columns(A::AbstractMatrix; [comparison]=isapproxzero)

Return all columns that have at least one non-zero entry.

Input

• A – matrix
• comparison – (optional; default: isapproxzero) function to check for equality with zero

Output

A vector of indices.

nonzero_indices(v::AbstractVector{N}) where {N<:Real}

Return the indices in which a vector is non-zero.

Input

• v – vector

Output

A vector of ascending indices i such that the vector is non-zero in dimension i.

projection_matrix(block::AbstractVector{Int}, n::Int, [N]::Type{<:Number}=Float64)

Return the projection matrix associated to the given block of variables.

Input

• block – integer vector with the variables of interest
• n – integer representing the ambient dimension
• N – (optional, default: Float64) number type

Output

A sparse matrix that corresponds to the projection onto the variables in block.

Examples

julia> proj = projection_matrix([1, 3], 4)
2×4 SparseArrays.SparseMatrixCSC{Float64, Int64} with 2 stored entries:
 1.0   ⋅    ⋅    ⋅
  ⋅    ⋅   1.0   ⋅

julia> Matrix(proj)
2×4 Matrix{Float64}:
 1.0  0.0  0.0  0.0
 0.0  0.0  1.0  0.0

rand_pos_neg_zerosum_vector(n::Int; [N]::Type{<:Real}=Float64,
                                    [rng]::AbstractRNG=GLOBAL_RNG)

Create a vector of random numbers such that the total sum is (approximately) zero, no duplicates exist, all positive entries come first, and all negative entries come last.

Input

• n – length of the vector
• N – (optional; default: Float64) numeric type
• rng – (optional; default: GLOBAL_RNG) random number generator

Output

A vector as described above.

Algorithm

This is the first phase of the algorithm described here.

rationalize(::Type{T}, x::AbstractArray{N}, tol::Real) where {T<:Integer, N<:AbstractFloat}

Approximate an array of floating point numbers as a rational vector with entries of the given integer type.

Input

• T – (optional, default: Int) integer type to represent the rationals
• x – vector of floating point numbers
• tol – (optional, default: eps(N)) tolerance the result at entry i will differ from x[i] by no more than tol

Output

An array of type Rational{T} where the i-th entry is the rationalization of the i-th component of x.

Notes

See also Base.rationalize.

rectify(x::AbstractArray{N}) where {N<:Real}

Rectify an array, i.e., take the element-wise maximum with zero.

Input

• x – array

Output

A copy of the array where each negative entry is replaced by zero.

remove_duplicates_sorted!(v::AbstractVector)

Remove duplicate entries in a sorted vector.

Input

• v – sorted vector

Output

The input vector without duplicates.

remove_zero_columns(A::AbstractMatrix)

Return a matrix with all columns containing only zero entries removed.

Input

• A – matrix

Output

The original matrix A if it contains no zero columns or otherwise a new matrix where those columns have been removed.

right_turn([O::AbstractVector{<:Real}=[0, 0]], u::AbstractVector{<:Real},
           v::AbstractVector{<:Real})

Compute a scalar that determines whether the acute angle defined by three 2D points O, u, v in the plane is a right turn (< 180° counter-clockwise) with respect to the center O.

Input

• O – (optional; default: [0, 0]) 2D center point
• u – first 2D point
• v – second 2D point

Output

A scalar representing the rotation. If the result is 0, the points are collinear; if it is positive, the points constitute a positive angle of rotation around O from u to v; otherwise they constitute a negative angle.

Algorithm

The cross product is used to determine the sense of rotation.

same_sign(A::AbstractArray)

Check whether all elements of the given array have the same sign.

Input

• A – array
• optimistic – (optional; default: false) flag for expressing that the expected result is true

Output

true if and only if all elements in A have the same sign.

Notes

The result is false if and only if the array contains two elements $e₁ > 0$ and $e₂ < 0$. Zero elements (0) do not influence the result.

samedir(u::AbstractVector{<:Real}, v::AbstractVector{<:Real})

Check whether two vectors point in the same direction.

Input

• u – first vector
• v – second vector

Output

(true, k) iff the vectors are identical up to a positive scaling factor k such that u = k * v, and (false, 0) otherwise.

Examples

julia> samedir([1, 2, 3], [2, 4, 6])
(true, 0.5)

julia> samedir([1, 2, 3], [3, 2, 1])
(false, 0)

julia> samedir([1, 2, 3], [-1, -2, -3])
(false, 0)

SingleEntryVector{N} <: AbstractVector{N}

A sparse unit vector with arbitrary one-element.

Fields

• i – index of non-zero entry
• n – vector length
• v – non-zero entry

substitute(substitution::Dict{Int, T}, x::AbstractVector{T}) where {T}

Apply a substitution to a given vector.

Input

• substitution – substitution (a mapping from an index to a new value)
• x – vector

Output

A fresh vector corresponding to x after substitution was applied.

substitute!(substitution::Dict{Int, T}, x::AbstractVector{T}) where {T}

Apply a substitution to a given vector.

Input

• substitution – substitution (a mapping from an index to a new value)
• x – vector (modified in this function)

Output

The same (but see the Notes below) vector x but after substitution was applied.

Notes

The vector x is modified in-place if it has type Vector or SparseVector. Otherwise, we first create a new Vector from it.

to_matrix(vectors::AbstractVector{VN},
          [m]=length(vectors[1]),
          [MT]=matrix_type(VN)) where {VN}

Input

• vectors – list of vectors
• m – (optional; default: length(vectors[1])) number of rows
• MT – (optional; default: matrix_type(VN)) type of target matrix

Output

A matrix with the column vectors from vectors in the same order.

to_negative_vector(v::AbstractVector{N}) where {N}

Negate a vector and convert to type Vector.

Input

• v – vector

Output

A Vector equivalent to $-v$.

 uniform_partition(n::Int, block_size::Int)

Compute a uniform block partition of the given size.

Input

• n – number of dimensions of the partition
• block_size – size of each block

Output

A vector of ranges, Vector{UnitRange{Int}}, such that the size of each block is the same, if possible.

Examples

If the number of dimensions n is 2, we have two options: either two blocks of size 1 or one block of size 2:

julia> uniform_partition(2, 1)
2-element Vector{UnitRange{Int64}}:
 1:1
 2:2

julia> uniform_partition(2, 2)
1-element Vector{UnitRange{Int64}}:
 1:2

If the block_size argument is not compatible with (i.e., does not divide) n, the output is filled with one block of the size needed to reach n:

julia> uniform_partition(3, 1)
3-element Vector{UnitRange{Int64}}:
 1:1
 2:2
 3:3

julia> uniform_partition(3, 2)
2-element Vector{UnitRange{Int64}}:
 1:2
 3:3

julia> uniform_partition(10, 6)
2-element Vector{UnitRange{Int64}}:
 1:6
 7:10

vector_type(T)

Return a corresponding vector type with respect to type T.

Input

• T – vector or matrix type

Output

A vector type that corresponds in some sense (see Notes below) to T.

Notes

• If T is a sparse vector or a sparse matrix, the corresponding type is also a sparse vector.
• If T is a regular vector (i.e. Vector) or a regular matrix (i.e. Matrix), the corresponding type is also a regular vector.
• Otherwise, the corresponding type is a regular vector.