4 ms·

Solving Problems with Decomposition

76 points by erwald 4y ago

siddboots 4y ago
Some more vocabulary for thinking about this is “analysis” and “synthesis”. Analysis is about breaking up a problem into isolated parts. Synthesis is reassembling the solved parts.
- kleene_op 4y ago
  I believe those translate nicely to the "top-down" and "bottom-up" approaches people often refer to when tackling difficult problems (like brain mapping).
workingon 4y ago
I was hoping for insight into a bunch of decomposition methods (SVD, POD, DMD, AA etc.). This was nice too. If anyone has any really good links discussing this type of decomposition please don’t hesitate to list some here for me :)
- spenrose 4y ago
  Notes on the Synthesis of Form is a weird, brilliant book defining a sort of meta-method for problem decomposition. It's the kind of book you'll love—if you like that kind of book ;-) https://www.designthatmatters.org/blog/2017/1/30/book-review-notes-on-the-synthesis-of-form https://www.designthatmatters.org/blog/2017/1/30/book-review...
karatinversion 4y ago
When solving problems with decomposition, it's often important to remember that the way you've decomposed the problem is part of your theory of what the solution will look like. If you feel like you're at a dead end on a subproblem, you might need to change the way you decompose the problem.
gerdusvz 4y ago
syntaxfree 4y ago
Grows more relevant each year: https://en.wikipedia.org/wiki/McNamara_fallacy?wprov=sfti1 https://en.wikipedia.org/wiki/McNamara_fallacy?wprov=sfti1
zxcvbnm 4y ago
Caveat: intern doesn't comprehend the problem, goes crazy with decomposition, there's an overengineered mess in the end. Now there's a 2nd puzzle: how is this mess supposed to solve that task. Which of the thousand-possible call chains, or search constraints, ended up with a particular result.
hnthrowaway0315 4y ago
I think the second difficulty is to know how to decompose. The first is to describe the problem clearly.
pcwelder 4y ago
This has been the single biggest learning for me as well, but in slightly different flavours: 1. In machine learning. For example, suppose you want to generate an article. If you try to build a model that sequentially generates all the words, you'll have a bad time. You won't be able to train a decent size LM on such a large sequence due to OOM. If you generate chunk by chunk each new chunk won't have previous context. The way you do is to decompose the problem: generate sections and subsections and may be a summary, then each paragraph gets conditioned on generated section and subsection, which can be generated parallely now. This type of solution appears in many many places in ML. 2. In a relational DB design. Having all the information of an entity in a single table is bad for building concurrent application. If you acquire a lock on a row a lot more users have to wait. Decomposing the data in multiple relational tables allows you to isolate changes. If you've a tree like dependency, the sibling tables can be worked on in parallel without any worry. 3. Codebase. If you've a single codebase with large number of people developing on it, you'll have slow development cycle. Decomposed codebase (and corresponding services) with relatively stable API as interface will allow you to have parallel development with less conflicts. You can get QA done in parallel, deployment can be parallel, refactor can be parallel, etc. 4. To get a numerical solution of PDE instead of parallelising all the matrix vector computations, you get much more natural and efficient method by decomposing physical domain (say a 3d space) and solving PDE on the subdomains with boundary conditions on the interfaces. This is known as domain decomposition method. These methods can be parallelized efficiently, but even sequentially they converge faster than then no decomposition! 5. In system and code design to reduce mental load. Isolation of a piece of logic or a service allows you to develop and maintain it effectively. If you've many services depending on many services, keeping a mental model of all the dependencies become challenging and creates a lot of points of failure.
jackblemming 4y ago
The 3rd bullet point has a name. It’s called structured programming (which is more than just goto = bad). I find it insulting the author lays out the introduction as if it’s his novel idea and off handedly includes one recent reference from 1999 as if it’s a modernish idea.

76 points by erwald 4y ago

Some more vocabulary for thinking about this is “analysis” and “synthesis”. Analysis is about breaking up a problem into isolated parts. Synthesis is reassembling the solved parts.

kleene_op 4y ago
I believe those translate nicely to the "top-down" and "bottom-up" approaches people often refer to when tackling difficult problems (like brain mapping).

workingon 4y ago

I was hoping for insight into a bunch of decomposition methods (SVD, POD, DMD, AA etc.). This was nice too. If anyone has any really good links discussing this type of decomposition please don’t hesitate to list some here for me :)

spenrose 4y ago
Notes on the Synthesis of Form is a weird, brilliant book defining a sort of meta-method for problem decomposition. It's the kind of book you'll love—if you like that kind of book ;-) https://www.designthatmatters.org/blog/2017/1/30/book-review-notes-on-the-synthesis-of-form https://www.designthatmatters.org/blog/2017/1/30/book-review...

karatinversion 4y ago

When solving problems with decomposition, it's often important to remember that the way you've decomposed the problem is part of your theory of what the solution will look like. If you feel like you're at a dead end on a subproblem, you might need to change the way you decompose the problem.

gerdusvz 4y ago

syntaxfree 4y ago

Grows more relevant each year: https://en.wikipedia.org/wiki/McNamara_fallacy?wprov=sfti1 https://en.wikipedia.org/wiki/McNamara_fallacy?wprov=sfti1

zxcvbnm 4y ago

Caveat: intern doesn't comprehend the problem, goes crazy with decomposition, there's an overengineered mess in the end. Now there's a 2nd puzzle: how is this mess supposed to solve that task. Which of the thousand-possible call chains, or search constraints, ended up with a particular result.

hnthrowaway0315 4y ago

I think the second difficulty is to know how to decompose. The first is to describe the problem clearly.

pcwelder 4y ago

This has been the single biggest learning for me as well, but in slightly different flavours: 1. In machine learning. For example, suppose you want to generate an article. If you try to build a model that sequentially generates all the words, you'll have a bad time. You won't be able to train a decent size LM on such a large sequence due to OOM. If you generate chunk by chunk each new chunk won't have previous context. The way you do is to decompose the problem: generate sections and subsections and may be a summary, then each paragraph gets conditioned on generated section and subsection, which can be generated parallely now. This type of solution appears in many many places in ML. 2. In a relational DB design. Having all the information of an entity in a single table is bad for building concurrent application. If you acquire a lock on a row a lot more users have to wait. Decomposing the data in multiple relational tables allows you to isolate changes. If you've a tree like dependency, the sibling tables can be worked on in parallel without any worry. 3. Codebase. If you've a single codebase with large number of people developing on it, you'll have slow development cycle. Decomposed codebase (and corresponding services) with relatively stable API as interface will allow you to have parallel development with less conflicts. You can get QA done in parallel, deployment can be parallel, refactor can be parallel, etc. 4. To get a numerical solution of PDE instead of parallelising all the matrix vector computations, you get much more natural and efficient method by decomposing physical domain (say a 3d space) and solving PDE on the subdomains with boundary conditions on the interfaces. This is known as domain decomposition method. These methods can be parallelized efficiently, but even sequentially they converge faster than then no decomposition! 5. In system and code design to reduce mental load. Isolation of a piece of logic or a service allows you to develop and maintain it effectively. If you've many services depending on many services, keeping a mental model of all the dependencies become challenging and creates a lot of points of failure.

jackblemming 4y ago

The 3rd bullet point has a name. It’s called structured programming (which is more than just goto = bad). I find it insulting the author lays out the introduction as if it’s his novel idea and off handedly includes one recent reference from 1999 as if it’s a modernish idea.