Score:1

Matrix multiplication circuit

pl flag

I am trying to understand which operations are computable by an $\texttt{NC}^1$ circuit. However, I am struggling to understand whether there is such a circuit for multiplying a matrix with a vector or if the circuit will necessarily be in $\texttt{NC}^2$.

Command Master avatar
in flag
Doesn't it have an arithmetic circuit of constant depth? That would imply it's in $\texttt{NC}^1$, I believe.
Score:0
ng flag

Say you have $A\in \mathbb{F}_p^{m\times n}$, and $s\in\mathbb{F}_p^n$. We want to compute $As\in\mathbb{F}_p^m$. Note that

  1. We can split this into $m$ computations of $\langle A_i, s\rangle$, where $A_i$ are the rows of $A$, i.e. it is $m$ $n$-dimensional inner products
  2. Each inner product can be computed in $\log_2(n)$ depth using $O(n)$ processors, essentially via putting each summand in $\langle A_i, s\rangle = \sum_{j = 1}^n A_{ij}s_j$ on the leaf of a full binary tree, and having each internal node sum the results of its two children. The root will then contain $\langle A_i, s\rangle$.

In total, with $O(mn)$ processors, we should be able to determine it in depth $O(\log n)$, provided the underlying arithmetic in $\mathbb{F}_p$ can be done in constant depth, which seems like a reasonable assumption. This would put it in $\mathsf{NC}^1$.

I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.