Solving Problems with Decomposition

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.

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.

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.

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 :)

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.

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.

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

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