13 ms·
When Math Gets Impossibly Hard
- 3pt14159 6y agoI know a military contractor working on some pretty cool stuff, especially back in the day. On one of their projects they had to solve some really gnarly partial differential equation and weren't really getting anywhere. Since what they actually wanted were values (not the algebraic solution) what they ended up doing is building the equivalent circuit and measured what the voltage and current was in the circuit to get the values that they needed for some completely different domain. I always thought that that way of thinking was pretty neat. Can the same abstraction have a different physical manifestation that's cheap to create? If you kinda squint a bit, it's what we do with computers.
- trenchgun 6y agoIsn't that just analog computing? Or is it something more fancy?
- enriquto 6y agoThis is analog computing, and it is really cool. Yet, I guess if it corresponds to a circuit it should be more an ODE than a PDE (unless your "circuit" involves large pieces of surface of non-uniform resistivity).
- 3pt14159 6y agoIt was a true PDE, not an ODE. The circuit was non-trivial, but though I knew PDEs at the time he told the story, I'd never used them on electronics (only heat / pressure flow, and other physical engineering stuff) so I couldn't really understand what he was saying.
- jonah-archive 6y agoYou can definitely do this! Check out Karplus's "Analog Simulation" for examples with conductive fluids and resistance networks: https://archive.org/details/analogsimulation0000karp https://archive.org/details/analogsimulation0000karp
- marcosdumay 6y agoYes. And a numerical calculus software would probably get there faster and with less work.
- jhayward 6y agoand higher precision.
- enriquto 6y agoNumerical solution of PDE is not really a solved problem. If your PDE involves shockwaves or turbulence (which happen for really simple PDEs) then the methods to compute solutions get incredibly fancy. There's no "black box" solution for numerical PDE, as there is for ordinary equations.
- marcosdumay 6y agoIf you can solve with an analog computer, without problems with metastability, oscillations or excessive noise, then you can solve it with numeric calculus too. Those computers have much more strict limitations than digital math.
- 3pt14159 6y agoI should call the guy up sometime and get the details about what they were working. It wasn't a run of the mill analog computer, but who knows how novel it really was.
- klyrs 6y agoYour description covers pretty much every quantum computer ever conceived. How certain are you?
- sudosysgen 6y agoNot sure you can call any of the actual quantum computers we've made "analog", but if you're talking about the quantum annealment machines, they are generally more limited and take longer than an equivalent supercomputing cluster.
- adamnemecek 6y agoIt is. I hope it comes back in the photonic form.
- curiousgal 6y agoBanks do that all the time with monte carlo simulation. Can't get a closed form solution? Simulate every possible outcome and aggregate them.
- filmor 6y agoThis is neither how a Monte-Carlo process works (it's sampling the possible outcomes randomly, not simulating all outcomes), nor what is described here (building a physical system where an observable value is described by the differential equation one is trying to solve).
- curiousgal 6y agoIn practice the number of simulated scenarii is quite large which is what I meant by "every". Not rigorous though, I concur. Monte Carlo methods are used to solve partial differential equations, I found both approaches similar in the sense that they look at how the system actually/could behave, instead of looking at the equations solely.
- stagehn 6y agoThis is a pedantic response. There isn't an important difference between building a physical system and building a system in code whose generating process is that which you're trying to model. And everyone knew he didn't mean every outcome literally.
- CPLX 6y agoYou’re talking more about goal-seeking functions right? That’s the one I always see in a finance context.
- seanhunter 6y agoWorked in the securities division of a leading investment bank for 8 years including on the equities exotics and hybrids trading desk. And I can confirm that we used to use MC whenever we had something we couldn't price using a closed form method. That said, it's a lot slower and more compute intensive so when you could use a grid pricer or pde solver or whatever people would use that instead. You're not really simulating every outcome, just a "large enough" representative sample. As an aside, my dad was a chemical engineer and Newton-Raphson was his equivalent everything-is-a-nail numerical method. We used to use brent root and monte carlo simulation in the same way. Numerical methods are awesome in general.
- jackfoxy 6y agoIsn't that the basis of analog computing? https://en.wikipedia.org/wiki/Analog_computer https://en.wikipedia.org/wiki/Analog_computer
- lopmotr 6y agoEngineers used to use the shape of a soap bubble to calculate the torsional stiffness or perhaps stress distribution of a non-circular shaft. http://www.newsteelconstruction.com/wp/wp-content/uploads/TechPaper/NSCMar12tech.pdf http://www.newsteelconstruction.com/wp/wp-content/uploads/Te...
- ghj 6y agoSoap film is also used to solve the steiner problem: https://www.youtube.com/watch?v=dAyDi1aa40E https://www.youtube.com/watch?v=dAyDi1aa40E
- kens 6y agoI've been doing some restoration on an analog computer. While it seems bizarre now to solve a problem with analog circuits instead of a digital computer, analog computers were a reasonable approach until about the 1970s. The basic idea of an analog computer is you use op amps to sum voltages. Integration is easy, by adding a capacitor. By hooking up op amps, capacitors, and resistors (usually with a plugboard), you can quickly and easily solve differential equations. (Surprisingly, multiplication by a non-constant value is hard with an analog computer.) The nice thing about analog computers is they gave the answer almost instantaneously. You could turn the dials and experiment with different parameters interactively. A digital computer in 1970, on the other hand, might take minutes to solve the same equation. This also made analog computers useful for real-time applications such as flight simulators. A big problem with analog computers is that the accuracy is limited by your components. If you want 0.1% accuracy, you need expensive 0.1% resistors and capacitors. With a digital computer, you can get as many bits of accuracy as you want using cheap components. Basically, Moore's law killed off analog computers.
- TrackerFF 6y agoJust fire up any older electronics textbook, and they'll probably have examples of integrator and summing circuits solving differential equations. At least that's what we had in our control (engineering) books.
- sudosysgen 6y agoIn my dad's Calculus II equivalent class in Morocco, one of the question in their exam was to built the circuit to solve a given differential equation. Pretty neat! That being said, that exam was substantially shorter and easier than the Cal II exam I had to take!
- qppo 6y ago> multiplication by a non-constant value is hard with an analog computer Researching this topic also qualifies you to write technobabble for sci-fi movies. Like "operational trans impedance amplifier."
- andrewjl 6y agoIs this something an FPGA or something similar could do? Would be interesting to know of any home-brew attempts at this out there.
- bashinator 6y agoI wonder how difficult it would be to re-purpose a modular analog audio synthesizer for this. Since they're direct descendants of analog computers in the first place.
- andrewjl 6y agoThere are ASICs out there that simulate analog synths, such Universal Audio. Brings to mind some interesting pure software approaches if that were the case.
- klyrs 6y agoDo you mean FPAA? Totally a thing. https://en.m.wikipedia.org/wiki/Field-programmable_analog_array https://en.m.wikipedia.org/wiki/Field-programmable_analog_ar...
- XMPPwocky 6y agoFPAAs don't really exist as products you can buy, as far as I know (unlike FPGAs, which are a very mature technology to the point that I suspect there's nontrivial (say, >5%) odds the average HN reader owns something with a FPGA in it somewhere.))
- andrewjl 6y agoI didn't know about this. It's curious that the article mentions that recently (2016) improved FPAAs were demonstrated. Perhaps an opportunity where there wasn't one before.
- dzolob 6y agoI knew a guy who built specific surfaces with plaster and threw marbles at them to find some special solutions to nonlinear mechanics problems. He thought of himself as an experimental mathematician.
- jiggawatts 6y agoThere is practically no scenario where a digital computer couldn't do better if what you wanted was a numerical result and not a symbolic one. It's simply criminal how underutilised the technique of Automatic Differentiation is! It can solve incredibly complex differentials to machine precision, good numerical stability, and minimal tuning or hand-holding. Lots of these "difficult" problems aren't, it's just that people aren't aware of the solution because it's not commonly taught in a University setting. Automatic Differentiation is one of those techniques that's "boring" and "numerical", so there are no courses that teach it.
- ampdepolymerase 6y agoDoesn't literally every optimisation and ML class teaches it nowadays?
- jiggawatts 6y agoActually, no! You would think so, but again, it's a boring numerical technique so it is all too often sidelined in favour of the more "flashy" symbolic techniques. An awful lot of tertiary education has been caught up in the publish-or-perish mentality. Unfortunately for AD, it is not "impressive". Differentiating hideously difficult expressions symbolically is impressive. Publishing a paper packed full of enormous, scary looking expressions is impressive. Merely saying that "we used AD and it worked just fine" is unimpressive. For decades now we've been incentivizing intellectual wankery over practical utility.
- lambdatronics 6y agoHere's an example from my field: "The derivatives of the finite-build coils are computed -- with almost no additional effort from the authors -- using automatic differentiation." Well, what kind of scientist are you, if you are too lazy to take derivatives? /sarcasm http://meetings.aps.org/Meeting/DPP20/Session/BP14.32 http://meetings.aps.org/Meeting/DPP20/Session/BP14.32
- theemathas 6y ago
- Loranubi 6y agoAlso see Optical Fourier co-processors for a similar example.
- m3kw9 6y agoMath is hard for me because once a step of a proof is lost on me, the whole thing is lost unless I branch out into a rabbit hole, and learn what just happened
- Eldandan 6y agoThat's part of what makes it such a rich subject. Even something as simple as writing y=sin(x) has so much more embedded into it than the "input x output y" notion of functions. Parametrization of the Unit Circle, right triangles, special angles, you name it. Diving into the rabbit hole enough to convince yourself the step is justified is part of the learning process, if you're engaging with it properly. You do need to be judicious sometimes with what you decide is important to dive further into. That comes with the context/goals and experience of the reader.
- ouid 6y agook, but all of those rabbit holes have bottoms. It just may be that the space in between represents a year or more of learning.
- iso8859-1 6y agoThey don't have bottoms, because at the bottom you have logical assumptions like e.g. classical logic. These only exist because of history, only because it was the easiest way for someone to say something "insightful". Going down the rabbit hole, you have to choose some arbitrary point to stop at; it would be a point at which you think that you can apply the knowledge you have gained so far, in a way that other people will "appreciate". Or you can just not stop, and try to go even deeper. But then you stop being a mathematician, and you turn into a madman, a philosopher or a theologist.
- drdeca 6y agoThe "rabbit hole" being discussed is just "understanding a step in an argument", not, providing a foundation for logic. It's not impossible to gain understanding of a step in someone else's argument.
- roywiggins 6y agoThe solution to gerrymandering is probably social, not mathematical, because the goals we want to pursue in district-drawing aren't strictly mathematical.
- thaumasiotes 6y agoIt bothers me that two arguments are commonly advanced for the idea that gerrymandering is a menace: 1. It lets politicians create districts that will vote for them no matter what. 2. It lets politicians waste opposition votes by putting them into districts that will, overall, just barely vote the other way. The problem is that these two visions of "the problem" directly oppose each other. #1 says that the problem is districts that vote an 80/20 split. #2 says the problem is districts that vote a 51/49 split.
- aaronblohowiak 6y agoThey aren’t necessarily in opposition to each other, though. Imagine having three districts of 60/40 instead of two districts of 90/10 and one of 0/100. In this way, the party in charge has effectively erased the substantial portion of the population that would support the opposition!
- thaumasiotes 6y agoWhat do you think the policy effects are in each case? In your second scenario, you have three politicians in two parties who are all basically unconstrained. In the first scenario, you have three politicians who all nominally belong to the same party, but their behavior is constrained much more sharply by the closeness of their districts.
- willturman 6y agoThese don't seem to contradict. It's entirely possible to carve up a rural area into sure-thing 60/40 districts, while carving up cities to be 55/45 while leaving a handful of 5/95 districts to the other party.
- 6y ago
- deleted 6y ago[deleted]
- ouid 6y ago>Many states require that districts be “compact,” a term with no fixed mathematical definition. Every open cover has a finite subcover.
- reallyeli 6y agoLogged in just to upvote this. I shudder to think what happens in those other states!
- lordnacho 6y agoNitpick: the bridge problem is impossible because there aren't 2 or 0 nodes of odd degree. If you have 2 islands with three bridges connecting them, you could just walk them trivially, yet there are an uneven number of connections on each node.
- dpbriggs 6y agoI may be misremembering my graph theory class, but isn't the necessary and sufficient conditions for an eulerian path just that every vertex needs to have even degree? I'm not sure how it could work if any nodes had odd degree.
- ogogmad 6y agoFor an Eulerian circuit, you need the graph to be connected and for every node to have even degree. For an Eulerian path (which doesn't have to start and end at the same point) you may also allow two vertices to have odd degree.
- dpbriggs 6y agoGot it, thanks!
- underanalyzer 6y agoIt’s sufficient but not necessary. Consider a trivial example with three nodes arranged in a chain. The edge nodes at the end of the chain both have degree 1 but walking from one edge to another is an eulerian path.
- dmurray 6y agoTFA specifies the bridge problem in the form where you have to "end up back home", so its conclusion is correct.
- gbjw 6y agoExcept that, if I understand correctly, the author poses the problem such that one must 'end up back home' (that is, one must find an Eulerian circuit, not a path). If there are 2 nodes of odd degree, then you must start at one and end at the other.
- bentona 6y agoThis might be incredibly pedantic, but since this is a mathematical philosophy article, I'm going to go ahead. These aren't "hard" problems, they're simply questions that don't make sense. Is finding an odd number that is divisible by 2 a "hard problem"? I don't think so, it's just that it turns out that it doesn't make sense to ask the question. Some of these "hard problems" actually have solutions that demonstrate they aren't solvable, and these solutions are fairly elegant, in which case I'd also say these are not "hard".
- LolWolf 6y agoI think that's the joke of the title, though; perhaps rephrased slightly: "no matter how hard you try, this mathematical problem cannot actually be solved (and we can prove it, too)."
- f154hfds 6y agoI've always found the perimeter over area close to the mark for jerrymandering but not quite good enough (because of the coastline paradox - forces picking an arbitrary segment size [1]). My idea - I welcome counter arguments - is to calculate the district's center of mass and find the furthest point the district still contains from that center of mass. Then create a circle with that distance as the radius and find the percentage of _land_ (maybe even privately owned land?) within that circle that is in the district. My view is that the percentage should be something like 50% (maybe higher? Hard to say without actually designing districts and checking the numbers). 50% would mean that half of the habitable land remaining in the circle could be a different district but no more. [1] https://en.wikipedia.org/wiki/Coastline_paradox https://en.wikipedia.org/wiki/Coastline_paradox
- bijection 6y agoWhat about perimeter vs area but let coastlines be counted as straight lines?
- f154hfds 6y agoThe coastline paradox extends to much more than coastlines - pretty much all natural boundaries I would think. It's certainly doable, it just seems to add extra variables to what really needs to be as foolproof as possible.
- bo1024 6y agoI don't think the coastline paradox has to apply, because we don't have to define the boundaries by existing geographical features like rivers or so on. Instead, you can simply put down a finite number of points on a map and define the districts using polygons (connect the points with straight lines.
- eat_veggies 6y agoOne interesting way of detecting gerrymandering that has been used in court [0] is to do a random walk on the graph of districting plans, where two plans have an edge between them if you can flip a precinct (the basic building block of a districting plan) in one plan to get the other plan. By randomly walking this graph, starting from the current plan and randomly flipping precincts, you can build a distribution of how compact the plans you saw were (there are some measures of compactness defined in TFA and the document linked below), and identify outliers, which are likely to be gerrymandered. [0] https://sites.tufts.edu/vrdi/files/2018/06/md-report.pdf https://sites.tufts.edu/vrdi/files/2018/06/md-report.pdf