1
$\begingroup$

NOTE: The tensors are considered row-major. The sequence of elements is preserved.

Let $A$ be a $m$-dimensional tensor of size $m_1 \times m_2 \times m_3 \cdots$ and $B$ be a $n$-dimensional tensor of size $n_1 \times n_2 \cdots$. Both have the same number of elements $(m_1 \cdot m_2 \cdot m_3\cdots) = (n_1 \cdot n_2 \cdots)$.

I have the index of one element in $A$: $(i_1, i_2, i_3, \cdots)$ and I want to find the index of the element with the same position in $B$: $(j_1, j_2,\cdots)$.

An example:

Let $A$ has dimensions $2 \times 2 \times 2$, and $B$ has dimensions $2 \times 4$.

I have index $(1,0,0)$ from $A$. I want to find the index of the corresponding element in $B$ using $(1,0,0)$ and the dimension information of $A$ and $B$.

What formula can I use?

Also, would the formula be different in the case of $m>n$ and $m<n$?

$\endgroup$
1
  • 1
    $\begingroup$ As it stands, the question doesn't have an unique answer. Take for instance $A\in\mathbb{R}^{2\times 2}$ and $B\in\mathbb{R}^4$: $B$ could be the columns of $A$ stacked, or its rows, or any permutation of its elements. You need to provide how you're transforming $A$ into $B$ to answer the question. $\endgroup$ Aug 10 at 13:28

1 Answer 1

1
$\begingroup$

The easiest way to do this is to imagine mapping from $A$ to a $1$-dimensional tensor, call it $C,$ and then then from $C$ to $B{:}$

$$A \to C \to B$$

  • $A$ is an $M$-dimensional tensor with dimensions $m_1 \times m_2 \times \cdots \times m_M$
  • $C$ is a $1$-dimensional tensor with $p$ elements
  • $B$ is an $N$-dimensional tensor with dimensions $n_1 \times n_2 \times \cdots \times n_N$
  • $m_1 m_2 \cdots m_M = p = n_1 n_2 \cdots n_N$

Using the zero-indexed row-major convention, we have

$$A[i_1, i_2, \ldots, i_M] = C[i_1 (m_2 m_3 \cdots m_M) + i_2 (m_3 m_4 \cdots m_M) + \cdots + i_{M-1} (m_M) + i_M],$$

or, equivalently,

$$\begin{align*} C[k] &= A[i_1, i_2, \ldots, i_M] \\ i_1 &= \left\lfloor \dfrac{k}{m_2 m_3 \cdots m_M} \right\rfloor \\ i_2 &= \left\lfloor \dfrac{k - i_1 (m_2 m_3 \cdots m_M)}{m_3 m_4 \cdots m_M} \right\rfloor \\ i_3 &= \left\lfloor \dfrac{k - i_1 (m_2 m_3 \cdots m_M) - i_2 (m_3 m_4 \cdots m_M)}{m_4 m_5 \cdots m_M} \right\rfloor \\ &\vdots \end{align*}$$

So, to map from $A[i_1,i_2,\ldots,i_M]$ to $B[j_1,j_2,\ldots,j_N],$ we have the following formula:

$$\begin{align*} k &= i_1 (m_2 m_3 \cdots m_M) + i_2 (m_3 m_4 \cdots m_M) + \cdots + i_{M-1} (m_M) + i_M \\ j_1 &= \left\lfloor \dfrac{k}{n_2 n_3 \cdots n_N} \right\rfloor \\ j_2 &= \left\lfloor \dfrac{k - j_1 (n_2 n_3 \cdots n_N)}{n_3 n_4 \cdots n_N} \right\rfloor \\ j_3 &= \left\lfloor \dfrac{k - j_1 (n_2 n_3 \cdots n_N) - j_2 (n_3 n_4 \cdots n_N)}{n_4 n_5 \cdots n_N} \right\rfloor \\ &\vdots \end{align*}$$


Sanity check: suppose $A = \begin{bmatrix} 10 & 20 & 30 \\ 40 & 50 & 60 \end{bmatrix}$ and $B = \begin{bmatrix} 10 & 20 \\ 30 & 40 \\ 50 & 60 \end{bmatrix}.$

  • Finding $B[j_1,j_2]$ corresponding to $A[1,0] = 40{:}$

$$\begin{align*} k &= 1(3) + 0 = 3 \\ j_2 &= \left\lfloor \dfrac{3}{2} \right\rfloor = 1 \\ j_1 &= 3 - 1(2) = 1 \\ B[1,1] &= 40 \quad \checkmark \end{align*}$$

  • Finding $B[j_1,j_2]$ corresponding to $A[0,2] = 30{:}$

$$\begin{align*} k &= 0(3) + 2 = 2 \\ j_2 &= \left\lfloor \dfrac{2}{2} \right\rfloor = 1 \\ j_1 &= 2 - 1(2) = 0 \\ B[1,0] &= 30 \quad \checkmark \end{align*}$$


(Edit) Further Simplification: (as pointed out by @user366312 in comment) To simplify further, you can replace $k \to k - j_1 (n_2 n_3 \cdots n_N)$ with $k \to k \mod (n_2 n_3 \cdots n_N),$ and so on:

$$\begin{align*} k &= i_1 (m_2 m_3 \cdots m_M) + i_2 (m_3 m_4 \cdots m_M) + \cdots + i_{M-1} (m_M) + i_M \\ j_1 &= \left\lfloor \dfrac{k}{n_2 n_3 \cdots n_N} \right\rfloor \\ j_2 &= \left\lfloor \dfrac{k \mod (n_2 n_3 \cdots n_N)}{n_3 n_4 \cdots n_N} \right\rfloor \\ j_3 &= \left\lfloor \dfrac{k \mod (n_2 n_3 \cdots n_N) \mod (n_3 n_4 \cdots n_N)}{n_4 n_5 \cdots n_N} \right\rfloor \\ &\vdots \end{align*}$$

$\endgroup$
6
  • $\begingroup$ Can this formula be made absolute rather than recursive? E.g., $j3$ is re-using $j1$ and $j2$. $\endgroup$
    – user366312
    Aug 10 at 17:16
  • $\begingroup$ I'm not aware of any closed-form solution, but if you do happen to find one, I'd love to hear about it. $\endgroup$ Aug 10 at 17:30
  • $\begingroup$ I have posted an answer. Could you check it? $\endgroup$
    – user366312
    Aug 10 at 17:39
  • $\begingroup$ Looks correct to me. You're just replacing $k \to k - j_1 (n_2n_3 \cdots n_N)$ with $k \to k \mod (n_2 n_3 \cdots n_N),$ and so on, which seems valid. $\endgroup$ Aug 10 at 17:55
  • $\begingroup$ Which one would be easier for computer implementation? $\endgroup$
    – user366312
    Aug 10 at 18:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .