Questions tagged [parallel]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
27 views

Compute a feasible schedule for scheduling on identical parallel machines?

I am considering the offline version of identical parallel machine scheduling with arrival time and deadlines while allowing preemption and no assumption regarding the agreeability of the arrival and ...
Walid Hanafy's user avatar
1 vote
0 answers
54 views

Pfaffian orientation algorithm for planar graphs

I was studying finding a pfaffian orientation of a planar graph in $NC$. In Vazirani's Paper on NC Algorithms for Computing the Number of Perfect Matchings in $K_{3,3}$-Free Graphs and Related ...
Soham Chatterjee's user avatar
2 votes
1 answer
187 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^n +i$ where $i\in\{-1,0,1\}$? Are these cases in $NC$? Are there any non-trivial classes of moduli ...
Turbo's user avatar
  • 12.8k
0 votes
0 answers
73 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 ...
anon2328's user avatar
-1 votes
1 answer
80 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 ...
Turkhan Badalov's user avatar
3 votes
1 answer
135 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 ...
anps's user avatar
  • 61
3 votes
0 answers
53 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
Dingo13's user avatar
  • 131
0 votes
0 answers
120 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 ...
hawkeye's user avatar
  • 2,581
9 votes
1 answer
420 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 ...
Libor's user avatar
  • 191
4 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 ...
rursw1's user avatar
  • 386
6 votes
0 answers
195 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 ...
Chad Brewbaker's user avatar