Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [decomposition]

The tag has no usage guidance.

1
vote
0answers
65 views

Decomposition of a bipartite graph into complete bipartite graphs by adding the smallest number of edges

A bipartite graph $G$ and an integer $K$ is given. I want to decompose $G$ into $K$ complete bipartite graphs by adding the smallest number of edges. Below is an example of decomposition when $K=2$. ...
0
votes
0answers
13 views

When BCNF decomposition preserves Functional Dependencies?

It is known that BCNF decomposition does not preserve functional dependencies (FDs). For example, for FDs on R(A,B,C), ...
1
vote
0answers
42 views

Polygon decomposition into minimum star-shaped polygons

As the title suggests, I'm trying to implement an algorithm to decompose a polygon into the minimum number of star-shaped polygons. I've been searching for quite some time but I can't find any ...
1
vote
1answer
30 views

What is the bit complexity of Gaussian eliminaton over $\Bbb F_q$?

Given matrix $M\in\Bbb F_q^{n\times n}$ with rank $r$ what is the complexity of converting to row-echelon form? Is it $O(n^3\log q)$ or $O(n^3q)$ bit operations? Technically $O(n^3)$ row ...
1
vote
0answers
17 views

Computational Considerations on least squares problems

I am reading Elements of Statistical Learning and read the following claim from the text (page 93, Chapter 3.7): Least squares fitting is usually done via the Cholesky decomposition of the matrix $\...
0
votes
1answer
359 views

Fine-Grain parallel algorithm for LU-decomposition

How would you understand this pseudocode of parallel algorithm for LU-decomposition ? I'm confused mostly with the min(i; j) - 1, because I have no idea, what ...
1
vote
1answer
1k views

Parallel algorithm for LU-decomposition

I need to implement LU-decomposition in Kaira. In Kaira the programmer writes the "parallel part" as the diagram similar to Petri Nets. So, could you, please, recommend me some parallel algorithms ...
0
votes
1answer
912 views

BCNF Decomposition: Confusion regarding given answer

I encountered the following question: Given a relation R(A, B, C, D) with the following functional dependencies: A -> B, C -> D, B -> C. The BCNF Decomposition of R is: A) {(A,B), (C,D), (B,C)} B) {...