rpjday@watrose.UUCP (rpjday) (10/15/86)
I am interested in collecting examples of problems in the area of computation that are generally acknowledged to be reasonably to obscenely difficult using the digital computer model, but which have simple elegant solutions if one was allowed to construct some form of "analog" computer. As an example, the problem of finding the shortest path between two points in a graph is easily solved if one is allowed to build a string model of the graph, then pick it up by the source node, and measure the distance straight down to the target node. I'm sure everyone is familiar with this trick, but I'm also sure there were other "analog" models of computation, some for supposedly intractable problems. Can anyone out there recall others, and mail them to me, or post them to the net? I will eventually summarize and repost to net.math (or sci.math, if that's what it is being renamed to). Thanx muchly. ______________________________________________________________________ R Day rpjday@watrose.uucp CS Department rpjday%watrose@waterloo.csnet U. of Waterloo rpjday%watrose%waterloo.csnet@csnet-relay.arpa
bradley@think.COM (Bradley Kuszmaul) (10/15/86)
In article <8194@watrose.UUCP> rpjday@watrose.UUCP (rpjday) writes: > > I am interested in collecting examples of problems in the area of >computation that are generally acknowledged to be reasonably to >obscenely difficult using the digital computer model, but which have >simple elegant solutions if one was allowed to construct some form >of "analog" computer. > As an example, the problem of finding the shortest path between two >points in a graph is easily solved if one is allowed to build a string >model of the graph, then pick it up by the source node, and measure the >distance straight down to the target node. I'm sure everyone is familiar >with this trick, but I'm also sure there were other "analog" models >of computation, some for supposedly intractable problems. > ... >R Day Summary of the rather long article which follows: (1) Finding the distance betwen two points in a graph can be solved efficiently on a digital computer. (2) The analog computer you propose must grow as fast as the problem (the crane to lift the string must grow). If I am allowed to build a digital computer which also grows then I can keep up with your analog computer by exploiting parallelism (e.g. using a Connection Machine (tm) computer system.) (3) The analog computer you propose does not even work. Point (1): I don't beleive that your example satisfies the requirements. Finding the shortest path between two points using a digital computer is nowhere near obscenely difficult. In fact it can be done in time which is only logarithmically worse than linear in the size of the graph by the following algorithm: To find the shortest distance (and in fact find a shortest path) from point A to point B in a (we'll even make it directed) graph G=(V,E) [vertices and edges]: Set each vertex's value to INFINITY Set set vertex A's value to 0. Let P be a priority queue, initialize P to contain A only. loop until P is empty Let V:= the smallest vertex in P (removing it from P) if V=A we are done. mark V as "VISITED" For each edge E from vertex V to vertex U, set U's value to MIN(U's old value, V's value + cost-of-edge(E)) if U is not "VISITED" and U's value just changed, then change U's position in the prioty queue to reflect its new value. end for end loop if we get here without V ever equalling A, then "you can't get there from here" Analysis: Clearly we are only going to examine any given vertex at most once (since we examine a vertex when it is the closest unexamined vertex, and examining a vertex which was further away is not going to make the closer vertex any closer than it already was). We also look at any given edge at most once, and we recompute U's position in the priority queue at most once per edge. Thus the only possible way for this algorithm to run in more than linear time is if munging around in the priority queue takes more than constant time. Well, the best priority queue algorithms I know take log time for each operation, giving us (N log N) time behavior for this algorithm. Point (2) The analog computer's "engine" grows with the size of the problem. If the digital computer is allowed corresponding growth, then parallelism can keep up: If we compare this to the problem of building a graph out of string and measuring it, we need to understand how fast building the graph really is. If we assume that graph has been built (which seems fair, since assume that the input to the algorithm above is ready to go), then it looks like the string algorithm takes time which is linear in the diameter of the graph (or some such nonesense). At any rate, it looks like the string has gained a linear speedup. However, this is not really fair, since there are some assumptions about how to implement this algorithm that have been ignored: For example, it takes a rather large hoist to implement the algorithm for billion vertex graphs, and we can conclude that the analog computer must grow as fast as the input grows. For the digital computer, the corresponding growth is in the memory components, but if your are going to charge me for the memory in my digital computer, I will respond by replacing every memory chip with a microprocessor chip, so that I can exploit parallelism too. (Then we get into an analysis of the performance of parallel algorithms to do the same thing, and what kind of interconnection network we are assuming between the processors...) Point (3) Another problem with the analog approach to solving this problem is that it does not work. Consider a family of graphs with bisection width which is linear in the number of vertices (e.g. in a binary hypercube containing N vertices, we have to cut N/2 edges in order to bisect the graph). Such a graph, when built out of string, and hung from a crane, starts getting fat around the center. The fact that the string has finite thickness is going to get us. Some of the strings will not hang straight down from point A to point B, but will have to take a slight horizonta detour to get around the other strings which are trying to get from point A to point B. - bradley@think.com or think!bradley
chandros@topaz.RUTGERS.EDU (Jonathan A. Chandross) (10/16/86)
/* Message-ID: <8195@watrose.UUCP> From: rpjday@watrose.UUCP (rpjday) */ ##> I am interested in collecting examples of problems in the area of ##>computation that are generally acknowledged to be reasonably to ##>obscenely difficult using the digital computer model, but which have ##>simple elegant solutions if one was allowed to construct some form ##>of "analog" computer. ##> As an example, the problem of finding the shortest path between two ##>points in a graph is easily solved if one is allowed to build a string ##>model of the graph, then pick it up by the source node, and measure the ##> distance straight down to the target node. I'm sure everyone is familiar The technique you are referring to is called "rubber banding." While workable for small problems, the method degrades quite substantially for large(r) problems. The problem of finding a shortest path for, say 1000 cities, will degrade to such an extent that one of the known heuristics, running on a digital computer, will outperform the analog version, both in accuracy and in time. The main reason that analog computing no longer flourishes is a result of 1) inaccuracy in calculations, and 2) difficulty in scaling models. Hopfield and Tank have come up with some amazing results for neural networks computing TSP (travelling salesmen problem). But it is very difficult to make the networks very large, and the component tolerence is not terrific. Fractional percent errors add up quickly. However, the topic is extremely interesting. People have built the seive of Erasthostenes (badly mangled spelling) out of bicycle rims and wire, and matrix multipliers out of (fundamentally) oatmeal boxes. Perhaps the topic could be expanded to bizarre analog computation in general?? Jonathan Chandross allegra!topaz!chandross
zdenek@heathcliff.columbia.edu (Zdenek Radouch) (10/16/86)
In article <6490@think.COM> bradley@godot.think.com.UUCP (Bradley Kuszmaul) writes: >In article <8194@watrose.UUCP> rpjday@watrose.UUCP (rpjday) writes: >> >> I am interested in collecting examples of problems in the area of >>computation that are generally acknowledged to be reasonably to >>obscenely difficult using the digital computer model, but which have >>simple elegant solutions if one was allowed to construct some form >>of "analog" computer. >> As an example, the problem of finding the shortest path between two >>points in a graph is easily solved if one is allowed to build a string >>model of the graph, then pick it up by the source node, and measure the >>distance straight down to the target node. I'm sure everyone is familiar >>with this trick, but I'm also sure there were other "analog" models >>of computation, some for supposedly intractable problems. >> ... >>R Day > >Summary of the rather long article which follows: > (1) Finding the distance betwen two points in a graph can be solved > efficiently on a digital computer. > (2) The analog computer you propose must grow as fast as the > problem (the crane to lift the string must grow). If I am > allowed to build a digital computer which also grows then I can keep > up with your analog computer by exploiting parallelism (e.g. > using a Connection Machine (tm) computer system.) > (3) The analog computer you propose does not even work. Sorry, my friend, you totally missed the point. The author of the original posting brought up a very interesting idea, namely, that some problems can be solved more efficiently on machines that are NOT digital computers. He has chosen an example to illustrate, what he's looking for, and he certainly got his idea across. Do you not like his example? It reminds me the recent FTL disscussion, that ended up with several net.physics readers concluding that all the confusion was caused by "massless and infinitely rigid rods" and similar objects, that can't really exist. It's not the models, what counts. It is HOW they get used! Summary of the rather long flame which follows: (1) You didn't convince me, that it would be more efficient for ME to use the computer insted of the strings. (2) The machine has to grow only because YOU made it too small in the first place. (3) The fact, that you can't add 2.3*10^456 + 1.2*10^789 on your calculator doesn't mean, that the calculator doesn't work. >I don't beleive that your example satisfies the requirements. Finding >the shortest path between two points using a digital computer is >nowhere near obscenely difficult.... > [The algorithm and its analysis deleted] Well, you needed 18 lines to describe the algorithm and 10 lines to explain it. He needed 25 words to describe his method. Then again, maybe I don't know what "simple and elegant" really means. >.... In fact it can be done in time >which is only logarithmically worse than linear in the size of the >graph by the following algorithm: His machine solves the problem in a time unit. I don't care if the time to run the algorithm is logarithmically worse than linear or exponentially better than quadratic. The algorithm is SLOWER! >.....For example, it >takes a rather large hoist to implement the algorithm for billion >vertex graphs......... > > For the digital computer, the corresponding growth is in the memory >components, but if your are going to charge me for the memory in my >digital computer, I will respond by replacing every memory chip with a >microprocessor chip, so that I can exploit parallelism too. Gee, that's really good idea! Replace every memory chip with a microprocessor chip in order to exploit parallelism! >Then we get into an analysis of the performance of parallel algorithms to do >the same thing, and what kind of interconnection network we are >assuming between the processors... One thing is for sure. The interconnection network has to be good enough to hold data for the bilion vertex graph... >Another problem with the analog approach to solving this problem is >that it does not work.... >The fact that the string has finite thickness is going to get us. Whereas the fact, that the word in Connection Machine (tm) computer system has finite length, is going to get martians. > - bradley@think.com or think!bradley The second one is more appropriate. zdenek ------------------------------------------------------------------------- Men are four: He who knows and knows that he knows, he is wise - follow him; He who knows and knows not that he knows, he is asleep - wake him; He who knows not and knows that he knows not, he is simple - teach him; He who knows not and knows not that he knows not, he is a fool - shun him! zdenek@CS.COLUMBIA.EDU or ...!seismo!columbia!cs!zdenek Zdenek Radouch, 457 Computer Science, Columbia University, 500 West 120th St., New York, NY 10027
zdenek@heathcliff.columbia.edu (Zdenek Radouch) (10/16/86)
There are many problems with "analog type solutions". In some cases we are interested only in the character of the solution (is the system stable? will it oscillate? is the output linear or exponential? etc.). There are other applications where "analog" solution gives us required precision. Many of these problems are too complex for digital computers and can be quite satisfactorily solved on devices known as "analog computers". I won't go into details, describing an analog computer, because everybody knows or can look at a representative - analog musical synthesiser. Similar devices are used in simulations of complex mechanical systems. If you ever tried to solve differential equation, compute a sine wave or exponential curve, you know, how difficult that is on a digital computer. But if you use a capacitor and an inductor (or mass and spring) you get second order differential equations, sine waves or exponentials with no difficulties at all! zdenek ------------------------------------------------------------------------- Men are four: He who knows and knows that he knows, he is wise - follow him; He who knows and knows not that he knows, he is asleep - wake him; He who knows not and knows that he knows not, he is simple - teach him; He who knows not and knows not that he knows not, he is a fool - shun him! zdenek@CS.COLUMBIA.EDU or ...!seismo!columbia!cs!zdenek Zdenek Radouch, 457 Computer Science, Columbia University, 500 West 120th St., New York, NY 10027
soussan@ihlpf.UUCP (Soussan) (10/17/86)
> > I am interested in collecting examples of problems in the area of > computation that are generally acknowledged to be reasonably to > obscenely difficult using the digital computer model, but which have > simple elegant solutions if one was allowed to construct some form > of "analog" computer. . . . > R Day rpjday@watrose.uucp > CS Department rpjday%watrose@waterloo.csnet > U. of Waterloo rpjday%watrose%waterloo.csnet@csnet-relay.arpa There was a fairly good (I think) discussion of this topic in _Scientific American_ in the "Computer Recreations" column recently (I'd look it up but I just move and all my SA's are still packed). I would guess that the discussion was in one of the early 1986 issues, but it may have been 85 (memory startin' to go...). It consisted of a discussion and a call for reader's ideas/examples, which were then revealed in the following month's column. It sounds like fun, so have some! Daniel Soussan
jmc@riccb.UUCP (Jeff McQuinn ) (10/21/86)
> There are many problems with "analog type solutions". In some cases we are > interested only in the character of the solution (is the system stable? > will it oscillate? is the output linear or exponential? etc.). There are > other applications where "analog" solution gives us required precision. > Many of these problems are too complex for digital computers and can be quite > satisfactorily solved on devices known as "analog computers". > I won't go into details, describing an analog computer, because everybody > knows or can look at a representative - analog musical synthesiser. > Similar devices are used in simulations of complex mechanical systems. > > zdenek One of the most fundemental approaches to engineering is to build a prototype. The prototype is in effect an analog model for computation. It becomes extraordinarily difficult to write software to simulate every nuance of a design when your not even sure what all your problems may be. Let's take an example of an extremely complex design which would be practically impossible to simulate on a digital computer. The Connection Machine tm. Computer models are great when it comes to doing many simulations on a well understood problem where a few variables are changed on each run. It can save both time and dollars. Analog models are unparalleled for finding that unexpected or little understood problems exist. The trade off is of course time and money to construct the prototype. Almost no one designs anything anymore without using both tools. Even basic research uses both tools extensively. We are building ever larger accelerators in an effort to model the conditions during the theroretical Big Bang. These are analog models for computation. Jeff McQuinn just VAXing around