# Questions tagged [dc.parallel-comp]

Theoretical questions in Parallel Computing

97 questions
Filter by
Sorted by
Tagged with
84 views

### Lower bounds on batched query search

I am not much in the field of databases. But the problem I m facing is the following: given a database $D$, we receive a batch of distinct queries $Q = \{q_1, ..., q _k\}$, where each $q_i$ is a ...
228 views

### $NC^i \subseteq DSPACE[\log^i{n}]$?

The containment $NC^1 \subseteq DSPACE[\log{n}]$ is simple and well-known (assuming a reasonable notion of uniformity for $NC^1$) and follows by: start with an $O(\log{n})$-depth polynomial sized ...
212 views

### Is conversion of PRAM to parameter number of processors trivial

In section 2 of chapter 4 of Kumar the idea of scaling down is discussed. It is mentioned that the naive method (emulating by assignment) can scale the complexity of the problem more then just "...
145 views

### Parallel algorithms to find the optimum of polynomials

Are there any non-trivial parallel algorithms to find the optimum (local or global) of polynomials? By trivial, I mean something which is an obvious application of a serial algorithm. For example, one ...
403 views

### Advantages and specific applications of massively parallel programming thesis idea

I'm nearly graduated in computer science engineering and my thesis should discuss the massively parallel computational model of CUDA and its advantages/applications. I'm searching for an application ...
200 views

### How is the iteration space of a nested for-loop containing two sequential nested loops represented?

In a general for loop of the form: for (i = 0, i <= n, i++) { for (j = i, j <= n, j++) ... for (k = i, k <= n, k++) ... } What ...
825 views

### What do people mean by capabilities and capacities?

Someone made a casual remark to me about the terminology of capabilities and capacities, in the context of threads, processors and runtime systems, particularly their theoretical modelling. For ...
130 views

### Reference request: reducing rank computations to characteristic polynomials over arbitrary rings

Question. I'm looking into certain algorithms for linear algebra which lie in NC2. Does anyone know of alternative references for the proof of the proposition just below, relating rank of matrices ...
1k views

### parallelizable fast matrix in-place transposition

what is the current state of the art in fast and parallel matrix in-place transposition? I would be very happy, if I could be given some pseudocode for this problem. As far as I could find papers, ...
783 views

### Is solving systems of equations modulo $k$ in $\mathsf{coMod}_k\mathsf L$ for $k$ composite?

I'm interested in the complexity of solving linear equations modulo k, for arbitrary k (and with a special interest in prime powers), specifically: Problem. For a given system of $m$ linear ...
264 views

### Most optimal parallel method for calculating the integral of a 2D function

I posted already this question to SO but got no answer so I try it now here: In some crunching number program, I have a function which can be just 1 or 0 in three dimensions. I do not know in advance ...
132 views

### Optimal parallel algorithm for finding roots of a function [closed]

In some problem I need to find the zeroes (multiple real solutions) of some functions in 1D and 2D. I wonder which is the best parallel algorithm for this, which can provide the highest accuracy and ...
196 views

### Algorithm for permuting elements using constant work space

I'm searching for an algorithm to do the following: A 1->3 B 2->6 C 4->5 D 5->2 E 6->4 F 3->7 G 8->9 H 10->11 Elements A-H are stored on ...
320 views

### Introductory notes on parallelization, in particular patterns of problems and algorithms

I am looking for online available Lecture notes or other resources that give a good introduction into parallel programming, just like parallel analog of basic classes in computer science. My focus is ...
336 views

### Recursive parallel topological sorting in linear time

While doing some research on topological sorting I came across a paper Parallel Topological Sorting Algorithm, TADA, A. and MIGITA, M. and NAKAMURA, R. which claims a recursive divide-and-conquer ...
435 views

### Parallel algorithms for reachability in directed planar graphs

Chong, Han and Lam showed that undirected st-connectivity can be solved on the EREW PRAM in $O({\log}n)$ time with $O(m+n)$ processors. What is the best known parallel algorithm for st-connectivity ...
328 views

### Parallel sorting: introduction and state of research

there seem to exist papers on parallel sorting, but I have not found a good introduction into this topic. So, do you know a good summary or introduction into parallel sorting algorithms? In ...
290 views

### Best algorithm for calculating lists of neighbours

Given a collection of thousands of points in 3D, I need to get the list of neighbours for each particle that fall inside some cutoff value (in terms of euclidean distance), and if possible, sorted ...
1k views

### Flynn's taxonomy, and “task parallelism and data parallelism”

Quoted from http://en.wikipedia.org/wiki/Task_parallelism: Task parallelism (also known as function parallelism and control parallelism) is a form of parallelization of computer code across ...
121 views

498 views

### Reducing complexity with parallelism

Is it possible (slash can you provide an example) to reduce computational complexity of a problem by using a parallel algorithm which does not require a number of processors relative to the input size?...