Movatterモバイル変換

Matrix multiplication of dyadic objects

Description

The standard matrix multiplication of twoDyadic-objects.

Usage

## S4 method for signature 'Dyadic,Dyadic'x %*% y

Arguments

Details

Both orders of multiplication are implemented:(scalar * dyadic) and(dyadic * scalar).

Value

Either aDyadic-object or a regular matrix depending on the structure typeof the input objects. The matrix outcome of multiplication is alsoreported as a message in the command line.

References

Kos, M., Podgórski, K., & Wu, H. (2025). Dyadic Factorization and Efficient Inversion of Sparse Positive Definite Matrices. arXiv. https://arxiv.org/abs/2505.08144

See Also

Dyadic-class for the definition of theDyadic-class;dyadFac for the dyadic decomposition of dyadic matrices;

Examples

#--------------------------------------------------##------- Multiplication of dyadic matrices --------##--------------------------------------------------#N <- 4k <- 3# Construct four types of dyadic matrices with made of 1'sV <- construct(N, k, type = "vert") # verticalH <- construct(N, k, type = "horiz") # horizontalS <- construct(N, k, type = "symm") # symmetricAS <- construct(N, k, type = "asymm") # asymmetric# Convert the dyadic matrices to matrix formatmat_V <- as.matrix(V)mat_H <- as.matrix(H)mat_S <- as.matrix(S)mat_AS <- as.matrix(AS)# Multiplication of dyadic matricesVV <- V %*% V # vertical * vertical = verticalHH <- H %*% H # horizontal * horizontal = horizontalHS <- H %*% S # horizontal * symmetric = asymmetricHV <- H %*% V # horizontal * vertical = asymmetricASV <- AS %*% V # asymmetric * vertical = asymmetricVH <- V %*% H # vertical * horizontal = non-dyadicVS <- V %*% S # vertical * symmetric = non-dyadicVAS <- V %*% AS # vertical * asymmetric = non-dyadicSS <- S %*% S # symmetric * symmetric = non-dyadicASAS <- AS %*% AS # asymmetric * asymmetric = non-dyadicASH <- AS %*% H # asymmetric * horizontal = non-dyadicdim(ASAS) # regular matrix

Arithmetic methods for Dyadic objects

Description

Implements arithmetic operations for Dyadic objects, including negation,addition, subtraction, and scalar multiplication.

Value

A Dyadic object representing the corresponding result of thearithmetic operation.

Methods

Unary ‘-’

Negates a Dyadic object.

‘+’

Adds two Dyadic objects.

‘-’

Subtracts one Dyadic object from another.

‘*’

Multiplies a Dyadic object by a scalar or vice versa.

References

Kos, M., Podgórski, K., & Wu, H. (2025). Dyadic Factorization and Efficient Inversion of Sparse Positive Definite Matrices. arXiv. https://arxiv.org/abs/2505.08144

See Also

Dyadic-class for the definition of theDyadic-class;as.matrix for extracting the matrix representationof aDyadic-object

Examples

#--------------------------------------------------------##-------- Arithmetic methods for dyadic objects ---------##--------------------------------------------------------#N <- 4k <- 3# Construct four types of dyadic matrices with made of 1'sV <- construct(N, k, type = "vert") # verticalH <- construct(N, k, type = "horiz") # horizontalS <- construct(N, k, type = "symm") # symmetricAS <- construct(N, k, type = "asymm") # asymmetric# Negation of dyadic objects (matrices)NegV <- -VNegV@typeall(as.matrix(NegV) == -as.matrix(V)) # Should be TRUE# Addition of dyadic objects (matrices)HpV <- H + V # horizontal + vertical = asymmetricHpV@type# Subtraction of dyadic objects (matrices)SmAS <- S - AS # symmetric - asymmetric = asymmetricSmAS@type# Scalar multiplication of dyadic objects (matrices)DoubleV <- 2 * V # Scalar multiplication does not change the typeVDouble <- V * 2 # Scalar multiplication does not change the typeDoubleV@typeVDouble@typeall(as.matrix(DoubleV) == 2 * as.matrix(V)) # Should be TRUEall(as.matrix(VDouble) == as.matrix(DoubleV)) # Should be TRUE# Linear combinationlinearComb <- -S + 3 * H - 6 * AS + V # linear combination of dyadic matriceslinearComb@type # "asymm"

The class to represent a dyadic matrix

Description

The main class in theDyadic-package used for representing three types of dyadic matrices: horizontal, vertical,symmetric, and asymmetric.

Value

runningnew("Dyadic") return an object that belongs to the classDyadic,with the initialization of the default values for the fields.

Slots

height

positive integer, the number of dyadic levels;

breadth

positive integer, the breadth of the dyadic structure;

type

string, one of the following character strings:horiz,vert,symm,asymm whichindicates the type of dyadic matrix

• horiz horizontal,

• vert vertical,

• symm symmetric,

• asymm asymmetric,

where the last two types distinguish symmetrically dyadic matrices (they both have symmetric dyadic structure)that correspond to symmetric or not symmetric matrices.

entries

list (of matrices); a list of the lengthheight containing(2^(l)-1)*breadth x 2^(height-l)*breadth matrices, wherel is the index running through the list.Each matrix in the list includes the entries corresponding to2^(height-l)(2^l-1)*breadth x breadth-matricesput side by side columnwise in thelth level of a dyadic structure. In the 'symm'- and 'asymm'-cases, the terms belowdiagonal on the diagonal blocks are set to zero.

aentries

list (of matrices); a list which is either empty if the slottype is not'asymm'or of the lengthheight otherwise, in which the case it contains(2^(l)-1)*breadth x 2^(height-l)*breadth matrices, wherel is the index running through the list.Each matrix in the list includes the entries corresponding to2^(height-l).(2^l-1)*breadth x breadth-matricesput side by side columnwise in thelth horizontal level of an asymmetric dyadic structure.The terms above and on the diagonal in the diagonal blocks are set to zero because they are accounted in the slotentries.

References

Kos, M., Podgórski, K., & Wu, H. (2025). Dyadic Factorization and Efficient Inversion of Sparse Positive Definite Matrices. arXiv. https://arxiv.org/abs/2505.08144

Examples

#-------------------------------------------------------------##------- Generating an object from the 'Dyadic' class --------##-------------------------------------------------------------## The most generic generation of an object of class 'Dyadic':D <- new("Dyadic") # a generic format for 'Splinets' objectD# The SLOTs of 'Dyadic' - the default valuesD@heightD@breadthD@typeD@entries[[1]]D@aentriesN <- 4k <- 3 # the height and breadth of a dyadic matrix# The construction of a horizontally dyadic matrix with height 4 and breadth 3.E <- list()for (i in 1:4) {    E[[i]] <- matrix(1, nrow = (2^(i) - 1) * 3, ncol = 2^(4 - i) * 3)}DD <- new("Dyadic", height = N, breadth = k, type = "horiz", entries = E)DD# The classic R matrix representation of DD.mat_DD <- as.matrix(DD)mat_DD

Extract aDyadic object from a numeric matrix

Description

This function extract aDyadic object ofgiven height and breadth from a classic matrix. If the correspondingsub-matrix extracted is not dyadic, the returned result will be wrong.

Usage

as.dyadic(mat, type, height, breadth)

Arguments

Details

This function converts a dyadic matrix of the classic matrixform into the correspondingDyadic object. If the input matrix isnot dyadic it extracts the entries for the dyadic structure of the givenheight and breadth that fits to the upper-left hand side corner. Entriesoutside the fitted dyadic structure are neglected even if they are notequal to zero.

Value

ADyadic object of the input type, height, and breadthrepresenting the input matrix.

See Also

Dyadic-class for a description of the class;

Examples

#-------------------------------------------------------------##------------Creating vertically dyadic matrices--------------##-------------------------------------------------------------#N <- 4k <- 3d <- k * (2^N - 1)mat1 <- matrix(0, nrow = d, ncol = d)mat2 <- matrix(0, nrow = d, ncol = d)for (i in 1:N) {    st_col_id <- (2^(i - 1) - 1) * k + 1    en_col_id <- (2^(i - 1) - 1) * k + k    for (j in 1:2^(N - i)) {        st_row_id <- st_col_id - (2^(i - 1) - 1) * k        en_row_id <- en_col_id + (2^(i - 1) - 1) * k        mat1[st_row_id:en_row_id, st_col_id:en_col_id] <-            as.matrix(rnorm((2^i - 1) * k^2), ncol = k, nrow = (2^i - 1) * k)        mat2[st_row_id:en_row_id, st_col_id:en_col_id] <-            as.matrix(rnorm((2^i - 1) * k^2), ncol = k, nrow = (2^i - 1) * k)        st_col_id <- st_col_id + 2^i * k        en_col_id <- en_col_id + 2^i * k    }}mat1mat2#-------------------------------------------------------------##----------Creating corresponding dyadic objects--------------##-------------------------------------------------------------#V1 <- as.dyadic(mat1, "vert", N, k) # A "vert" dyadic objectV2 <- as.dyadic(mat2, "vert", N, k) # A "vert" dyadic objectmat1S <- t(mat1) %*% mat1 # A symmetrically dyadic matrixmat1AS <- t(mat2) %*% mat1 # An asymmetrically dyadic matrixS <- as.dyadic(mat1S, "symm", N, k) # A "symm" dyadic objectAS <- as.dyadic(mat1AS, "asymm", N, k) # A "asymm" dyadic objectall(as.matrix(S) == mat1S) # Should be TRUE.all(as.matrix(AS) == mat1AS) # Should be TRUE.#-------------------------------------------------------------##---------------Creating a non-dyadic matrices----------------##-------------------------------------------------------------#mat3 <- diag(d + 5)mat3[1:d, 1:d] <- mat1V3 <- as.dyadic(mat3, "vert", N, k) # Extract the upper-left dxd dyadic sub-matrixall(as.matrix(V3) == mat1) # Should be TRUE.

Matrix representation of dyadic objects

Description

Extracting the matrix representationof aDyadic-object.

Usage

## S4 method for signature 'Dyadic'as.matrix(x)

Arguments

Details

The dyadic structure contains information about the type of matrix and its width and height.

Value

The result is awidth*(2^height-1) x width*(2^height-1) matrix.

References

Kos, M., Podgórski, K., & Wu, H. (2025). Dyadic Factorization and Efficient Inversion of Sparse Positive Definite Matrices. arXiv. https://arxiv.org/abs/2505.08144

See Also

Dyadic-class for the definition of theDyadic-class;dyadFac for the dyadic decomposition of dyadic matrices;

Examples

#--------------------------------------------------------##------- Matrix representation of dyadic objects --------##--------------------------------------------------------#N <- 4k <- 3# Construct four types of dyadic matrices with made of 1'sV <- construct(N, k, type = "vert") # verticalH <- construct(N, k, type = "horiz") # horizontalS <- construct(N, k, type = "symm") # symmetricAS <- construct(N, k, type = "asymm", distr="norm") # asymmetric# Convert the dyadic matrices to matrix formatmat_V <- as.matrix(V)mat_H <- as.matrix(H)mat_S <- as.matrix(S)mat_AS <- as.matrix(AS)

Construction of aDyadic object

Description

The function constructs aDyadic object eitherwith random entries (default) or with entries equal to one.

Usage

construct(height, breadth, type = "vert", distr = "nonrand", param = c(0, 1))

Arguments

Details

The function constructs a genericDyadic-object of any type andin the case of thesymm type with random entries the object represents a symmetric matrix.

Value

ADyadic-object.

References

Kos, M., Podgórski, K., & Wu, H. (2025). Dyadic Factorization and Efficient Inversion of Sparse Positive Definite Matrices. arXiv. https://arxiv.org/abs/2505.08144

See Also

Dyadic-class for a description of the class.

Examples

#-------------------------------------------------------------##---Building 'Dyadic' objects of arbitrary types and sizes ---##-------------------------------------------------------------#N <- 4k <- 3 # the height and breadth of a dyadic matrix# Nonrandom vertical dyadic matrix with entries equal to 1S <- construct(N, k)S@entries[[N]] # The top level entriesS@entries[[1]] # The bottom level entriesS@type <- "horiz"# 'S' becomes horizontaly dyadic matrix,# which is the transpose of the original object# Symmetric dyadic with entries equal to 1SS <- construct(N, k, type = "symm")SS@entries[[2]] # The second bottom level entriesSS@aentries # This list is empty whenever the type is not 'asymm'# Asymmetric dyadic with entries equal to oneAS <- construct(N, k, type = "asymm")AS@entries[[2]] # The second bottom level entriesAS@aentries[[2]]# The asymmetric version# (which happens to be also symmetric in this case)# Truly asymmetricAS <- construct(N, k, type = "asymm", distr = "unif")AS@entries[[2]] # The second bottom level entriesAS@aentries[[2]] # The second bottom level asymmetric entries

Efficient factorization of a positive definite symmetrically dyadicmatrix.

Description

This function implement the efficient factorization of apositive definite symmetrically dyadic matrix\boldsymbol \Sigma.It computes the vertically dyadic matrix\mathbf P such that\mathbf P^\top \boldsymbol \Sigma \mathbf P = \mathbf I.

Usage

dyadFac(S, inv = FALSE, band = FALSE)

Arguments

Details

This function implement the efficient factorization of apositive definite symmetrically dyadic matrix.

Value

Ifinv == TRUE, then the inverse of\boldsymbol \Sigma,which is a(2^(height)-1)*breadth x (2^(height)-1)*breadth classicmatrix, is returned. Otherwise, the verticallyDyadic object for\mathbf P is returned.

See Also

Dyadic-class for a description of the class;

Examples

#-------------------------------------------------------------##---------Inverting a PD symmetrically dyadic matrix----------##-------------------------------------------------------------#N <- 4k <- 3# A 45x45 vertically dyadic matrixV <- construct(N, k, type = "vert", distr = "unif")# A 45x45 symmetrically dyadic matrixS <- t(V) %*% VS@type <- "symm"S@aentries <- list() # Convert S from "asymm" to "symm"# Check what S looks likematS <- as.matrix(S)matS# Find the vertically dyadic matrix that satisfies P^T S P = I# using a dyadic factorization algorithm.P <- dyadFac(S)I1 <- as.matrix(t(P) %*% S %*% P)I <- diag(dim(I1)[1])max(abs(I1 - I)) # Should be trivially small# Obtain the inverse of S via the dyadic algorithmiS <- dyadFac(S, inv = TRUE)I2 <- iS %*% matSmax(abs(I2 - I)) # Should be trivially smalliS_solve <- solve(matS)I3 <- iS_solve %*% matSmax(abs(I3 - I)) # The result obtained using built-in method for inversion#-------------------------------------------------------------##-----------------Inverting a PD band matrix------------------##-------------------------------------------------------------#d <- k * (2^N - 1)half_B <- matrix(0, nrow = d, ncol = d)for (i in 1:d) {    half_B[i, i:min(d, (i + k - 1))] <- rnorm(min(d, (i + k - 1)) - i + 1, mean = N, sd = 1 / N)}matB <- t(half_B) %*% half_B # matB is a PD band matrix with half bandwidth 3.# Convert matB into a dyadic object BB <- as.dyadic(matB, "symm", N, k)iB <- dyadFac(B, inv = TRUE)I <- diag(dim(matB)[1])max(abs(iB %*% matB - I)) # Should be trivially smalliB_band <- dyadFac(B, inv = TRUE, band = TRUE)max(abs(iB_band %*% matB - I)) # Should be trivially smalliB <- dyadFac(B)iB_band <- dyadFac(B, band = TRUE)max(abs(as.matrix(iB) - as.matrix(iB_band))) # Should be trivially small

Transpose of aDyadic object

Description

TheDyadic object transpose of aDyadic object:t(Dyadic).

Usage

## S4 method for signature 'Dyadic't(x)

Arguments

Details

The operations are performed in a way that is consistent with the dyadic structure of the matrices.

Value

TheDyadic-object that is the result of the operation with properly defined fields.

References

Kos, M., Podgórski, K., & Wu, H. (2025). Dyadic Factorization and Efficient Inversion of Sparse Positive Definite Matrices. arXiv. https://arxiv.org/abs/2505.08144

See Also

Dyadic-class for the definition of theDyadic-class;dyadFac for the dyadic decomposition of dyadic matrices;

Examples

#--------------------------------------------##-------Transpose of a dyadic object --------##--------------------------------------------#N <- 4k <- 3# Construct four types of dyadic matrices with made of 1'sV <- construct(N, k, type = "vert") # verticalH <- construct(N, k, type = "horiz") # horizontalS <- construct(N, k, type = "symm", distr = "unif") # symmetrict(V)@type # The transpose of a vertical dyadic matrix is horizontalt(H)@type # The transpose of a horizontal dyadic matrix is verticalall(as.matrix(t(V)) == t(as.matrix(V))) # Should be TRUEall(as.matrix(S) == as.matrix(t(S))) # Should be TRUE