Questions tagged [parallel]
The parallel tag has no usage guidance.
9
questions
1
vote
0
answers
61
views
On parallel complexity of modular inverse
Modular inverse is not known to be in $NC$ either.
How about the cases where the modulus is just $2^k +i$ where $i\in\{-1,0,1\}$?
Are these cases in $NC$?
- 12.6k
0
votes
0
answers
61
views
Unclear explanation of basic parallel DAG computation
Consider computation represented as a DAG, without if-then-else conditions, where nodes represent tasks and edges represent data dependencies. For example, A->B->C means that there are 3 tasks ...
- 1
-1
votes
1
answer
78
views
How to know if a problem is distributable?
I am new to the world of Parallel computing and that is why don't know exactly where I should look at or search to get the answer.
Is there any theorem or just general theory determining which code ...
3
votes
1
answer
124
views
parallel algorithms for the determinant of the Hessenberg matrix
I am interested in highly parallel algorithms for computing the determinant of matrices of a special form (over finite fields).
It is known that computing determinant of general matrices over finite ...
- 61
3
votes
0
answers
52
views
Best complexity bound for parallel matrix-vector product?
I'm looking for the best known complexity (and a bound for the number of processors invoved) to do the calculation of a $(n,n)$ matrix-vector product.
Thank you
- 131
0
votes
0
answers
119
views
Is Ralf Hinze's Discriminator sort parallelizable?
According to this slide - the following sorting algorithms
Merge Sort
Insertion Sort
Bubble Sort
Quicksort
Bogosort
all rely on cmp - which has a fixed upper ...
- 2,541
9
votes
1
answer
415
views
Finding optimal parallelization from general weighted undirected graph
I am solving a problem of "blending" sets of overlapping images. These sets can be represented by undirected weighted graph such as this one:
Each node represents an image. Overlapping images are ...
CommunityBot
- 1
3
votes
0
answers
2k
views
Linear programming optimization problems using parallel algorithms
I'm looking for methods and algorithms for solving linear programming algorithms, characterized by up to 20 variables but up to thousands of constraints in a parallel way. There are several approaches ...
- 376
6
votes
0
answers
194
views
Complexity of Roman numeral evaluation
I came up with a result the other day that arbitrary length Roman numeral evaluation can be modeled as a monoid:
https://gist.github.com/4542999
1) Is this a known result?
2) If not, any ...
- 2,351