Skip to main content

Questions tagged [decomposition]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
5 votes
2 answers
1k views

Global optimization of state assignments in a directed graph with a tree-based distance cost

I am exploring a general optimization framework to solve problems characterized by the following structure. Any literature references, search terms, or algorithmic strategies would be greatly ...
Rolf Rolles's user avatar
1 vote
1 answer
153 views

Learning eigenvalue decomposition

How would you build a fully connected neural network that learns eigenvalue decomposition efficiently? I wanted to build NNs that can predict certain properties about matrices which are NP-hard to ...
Arjo's user avatar
  • 113
1 vote
1 answer
57 views

Relationships between path width and clique size of interval graphs

I faced the following claim on wikiepdia about interval graphs (https://en.wikipedia.org/wiki/Interval_graph): The pathwidth of an interval graph is one less than the size of its maximum clique. I ...
user20519169's user avatar
-1 votes
1 answer
391 views

Converting a Directed Acyclic Graph to a Directed Tree

I'm wondering if anyone can help me with this. Say I have a DAG, I understand that it has no directed cycles, but it can have loops ( "diamonds" ). My question is, is there a known way to ...
T-Tory's user avatar
  • 9
-1 votes
1 answer
105 views

Integer decomposition algorithm

Suppose I have a 32-bit integer $x$, I want to find $\{ x_i \}_{i \in 1\dots\ell}$ such that $x = e + \sum_{i=1}^\ell x_i \cdot 2^{32 - B\cdot i}$ where the error $e$ is as small as possible. The ...
lamba's user avatar
  • 107
0 votes
0 answers
183 views

Is this decomposition in 3NF?

I have the following question: Consider relation R(A, B, C, D, E, F, H) with the following functional dependencies: A --> D, AE --> H, DF --> BC, E --> C, H --> E Consider three ...
rigidweight's user avatar
0 votes
1 answer
145 views

decomposition to BCNF

Given $R$=($A,B,C,D,E,G$), And $F_c$={$A$$\rightarrow$$E$ ,$E$$\rightarrow$$ACD$ ,$BD$$\rightarrow$$E$, $CD$$\rightarrow$$B$} Candidate keys are: $GA, GE, GDB, GCD$ Lets say I pick the FD $A$$\...
Omri Braha's user avatar
4 votes
1 answer
139 views

One-dimensional packing problem: Optimal decomposition of music structure

I am currently working on my Master thesis on the visualization of music structure and I'm looking to find an optimal description of repetitions found in a piece of music. Problem Description Given a ...
Job Savelsberg's user avatar
3 votes
1 answer
258 views

Applying SVD compression to integral point images

Suppose that we have an $m\times n$ matrix $A$ of rank $n$, whose entries are 8-bit unsigned integers obtained from a grayscale image. Now we want to apply SVD to $A$ and to use the first $k$ singular ...
Peradventure's user avatar
4 votes
1 answer
120 views

Term for a graph decomposition based on a maximum matching

Let $M$ be a maximum cardinality matching in a bipartite graph $G(X+Y,E)$. Let $X_0$ be the subset of $X$ unmatched by $M$. Define the following sequence: $Y_1 = $ the neighbors of $X_0$ using edges ...
Erel Segal-Halevi's user avatar
1 vote
0 answers
204 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$. ...
kivantium's user avatar
1 vote
0 answers
213 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 ...
John Katsantas's user avatar
1 vote
1 answer
41 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 ...
Turbo's user avatar
  • 2,911
1 vote
0 answers
19 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 $\...
cgo's user avatar
  • 273
0 votes
1 answer
541 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 the ...
Eenoku's user avatar
  • 242
1 vote
1 answer
2k 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 ...
Eenoku's user avatar
  • 242
0 votes
1 answer
1k 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) {...
Abhishek Bansal's user avatar