<p>I am trying to understand how word sizes in a problem affects complexity. The question could be a simple technicality I am trying to clarify since I am not from mainstream CS. Let $V$ be an $n \times n$ fixed Vandermonde matrix and $A$ an $n \times 1$ arbitrary vector. Both $V$ and $ A$ have entries in $\mathbb{Z}$. Both $VA$ and $V^{T}A$ can be calculated in $O(n\log^{a}n)$ multiplications and additions on a fixed word machine ($a$ is a positive constant).</p>

<p><a href="http://www2.cs.uh.edu/~ooo00a/reading/fast_algorithms_with_preprocessing_for_matrix-vector_multiplication_problems.pdf" rel="nofollow">http://www2.cs.uh.edu/~ooo00a/reading/fast_algorithms_with_preprocessing_for_matrix-vector_multiplication_problems.pdf</a></p>

<p>Does the above complexity result hold when $V$ is generated by a number of size $O(\log^{b}{n})$ bits where $b$ is a positive constant? In this case, the highest number in $V$ is of size $O(n\log^{b}{n})$ bits. Shouldn't this have an impact?</p>

CC BY-SA 3.0
2011-05-17T13:50:02.890Z
I am beginning to see your point.
Turbo
CC BY-SA 3.0
2011-05-17T16:58:05.170Z
The reason I am asking is due to a related problem, given the $n^{th}$ column of $V$ which are powers of $X^{n-1}$ where $X$ generates $V$ and a matrix $B$ whose entries are of size $O(\log n)$, it seems impossible to find the vector $BV$ in $O(n\log^{b}(n))$ complexity since $V$ has words of size $O(n\log^{b}(n))$ and one has to multiply $n^2$ elements of $B$ with individual elements of $V$. Is my reasoning on bit complexity wellfounded in this case?
Turbo
<cc.complexity-theory><matrix-product>
Question on size of words in Vandermonde Matrix - Vector multiplication complexity
Turbo
# Question on size of words in Vandermonde Matrix - Vector multiplication complexity

(Asked by: username_0 on 2011-05-08)

I am trying to understand how word sizes in a problem affects complexity. The question could be a simple technicality I am trying to clarify since I am not from mainstream CS. Let $V$ be an $n \times n$ fixed Vandermonde matrix and $A$ an $n \times 1$ arbitrary vector. Both $V$ and $ A$ have entries in $\mathbb{Z}$. Both $VA$ and $V^{T}A$ can be calculated in $O(n\log^{a}n)$ multiplications and additions on a fixed word machine ($a$ is a positive constant).

<http://www2.cs.uh.edu/~ooo00a/reading/fast_algorithms_with_preprocessing_for_matrix-vector_multiplication_problems.pdf>

Does the above complexity result hold when $V$ is generated by a number of size $O(\log^{b}{n})$ bits where $b$ is a positive constant? In this case, the highest number in $V$ is of size $O(n\log^{b}{n})$ bits. Shouldn't this have an impact?

**Tags:** cc.complexity-theory, matrix-product
> **Comments:**
> **username_0**: I am beginning to see your point.  
> **username_0**: The reason I am asking is due to a related problem, given the $n^{th}$ column of $V$ which are powers of $X^{n-1}$ where $X$ generates $V$ and a matrix $B$ whose entries are of size $O(\log n)$, it seems impossible to find the vector $BV$ in $O(n\log^{b}(n))$ complexity since $V$ has words of size $O(n\log^{b}(n))$ and one has to multiply $n^2$ elements of $B$ with individual elements of $V$. Is my reasoning on bit complexity wellfounded in this case?  

---

## 0 answers

