On Fri, May 05, 2023 at 03:22:49PM -0600, Stephen Guerin wrote: > I think that's the same as when I said "I knew how to solve n-body systems > with > particle N^2/2 forces (corrected) with some quadtree or octree optimizations > to > get from n^2 to nlog(n)." . Or are you saying something different? >
Similar. Quad/Octrees are good for inhomgenous simulations. Particle in cell methods are for homogenous simulations. Note a technique I developed in conjuction with Duraid Madina in the early noughties which we called GraphCode is effectively a particle-in-cell method on an arbitrary graph. The graph can change dynamically, and the cells redistributed to rebalance a calculation using a graph partitioning algorithm - it makes for something more general than quad/octrees. I have written this up a couple of times, but have moved on to other things now, and the work has had little impact. But I did discover that a Spanish group took my code to develop an ABM system that was as least twice as performant as the equivalent model in RepastHPC, so we obviously did somethig right (J. Supercomputing, 2018, doi:10.1007/s11227-018-2688-8). > > On Fri, May 5, 2023 at 2:58 PM Angel Edward <edward.an...@gmail.com> wrote: > > Here’s another connection I had forgotten. Consider particles on a 2D > rectangle with 1/r^2 repulsion. If you break up the rectangle into > smaller > rectangles in which particles can only stay in their own rectangles or > move > to neighbor rectangles, the N^2 force calculation comes down to N log N, > same as the limit on good sorting algorithms. This technique came up when > we were using particles to form an isosurface in 3D. > > Ed > __________ > > Ed Angel > > Founding Director, Art, Research, Technology and Science Laboratory (ARTS > Lab) > Professor Emeritus of Computer Science, University of New Mexico > > 1017 Sierra Pinon > Santa Fe, NM 87501 > 505-984-0136 (home) edward.an...@gmail.com > 505-453-4944 (cell) http://www.cs.unm.edu/~angel > > > On May 5, 2023, at 2:31 PM, Stephen Guerin > <stephen.gue...@simtable.com > > wrote: > > Thanks Roger and Ed! > > I've spent some time with Ed and Frank discussing this and I've really > filled in some gaps in my knowledge of parallel algorithms. eg, I knew > how to solve n-body system with particle N^2/2 focus with some > quadtree > or octree optimizations to get from n^2 to nlog(n). But the FFT > transform on laplacians solving Poisson equation was new to me and I > can now see the beauty. Today, Ed quickly threw out the Kronecker > Operator/Product which Frank knew but I didn't. Frank flashed me a > wikipedia article on his phone with symbolics that I couldn't > immediately grok. But asking chatGPT to explain the operator to a 3D > graphics person I immediately got it and had the benefit that I would > usually implement this function with two inner loops over rows and > columnts instead of using Kronecker available in optimized linear > algebra/graphics libraries. Often this was happening under the hood of > my tools but didn't realize it. > > As a 3D graphics developer, understanding the Kronecker matrix can be > very useful. The Kronecker product is often used in computer graphics > and computer vision applications, such as texture mapping, geometric > transformations, and image processing. Here are a few specific ways in > which Kronecker matrix can be useful to a 3D graphics developer: > 1. Texture mapping: The Kronecker product can be used to create > repetitive patterns in textures, such as brick walls, tiles, or > grass. By creating a base texture and applying a Kronecker product > with a smaller texture, a developer can create a seamless and > repeating texture that covers a larger surface. > 2. Geometric transformations: The Kronecker product can be used to > perform geometric transformations, such as scaling, rotation, and > translation, on 3D objects. By creating a Kronecker matrix with a > transformation matrix, a developer can apply the transformation to > every vertex of an object, resulting in a transformed object. > 3. Image processing: The Kronecker product can be used to perform > image processing operations, such as blurring, sharpening, or edge > detection, on 3D images. By creating a Kronecker matrix with a > filter matrix, a developer can apply the filter to every pixel of > an image, resulting in a processed image. > In summary, the Kronecker matrix is a powerful tool that can be used > in > various ways by 3D graphics developers. Whether it's creating > textures, > transforming objects, or processing images, understanding the > Kronecker > matrix can help a developer achieve their desired results more > efficiently and effectively. > > > > > _______________________________________________________________________ > stephen.gue...@simtable.com > CEO, https://www.simtable.com > 1600 Lena St #D1, Santa Fe, NM 87505 > office: (505)995-0206 mobile: (505)577-5828 > > > On Fri, Apr 28, 2023 at 7:50 PM Angel Edward <edward.an...@gmail.com> > wrote: > > Most of my dissertation (1968) was on numerical solution of > potential problems. One of the parts was a proof that some of the > known iterative methods converged. The argument loosely went > something like this. Consider the 2D Poisson equation on a square. > If you use an N x N approximation with the usual discretization of > the Laplacian > > u_ij = (u_i(j-1) + u_i(j+1) + u_(i_1)j + i_(j+1))/4 > > i.e, the average of the surrounding points, the problem reduces to > the solution of a set of N^2 linear equations > > Ax = b > > where x in a vector of the unknown {u_ij} arranged by rows or > columns, b is determined by the boundary conditions and the right > side of the Poisson equation. The interesting part is A which is > block tridiagonal. With only a small error A can be made block > cyclic. You can then diagonalize A with a sine transform and I was > able to use that for proofs. > > A few years later when the FFT came about, we realized that we > could use the FFT to do the sine transform and the resulting > numerical method was as least as efficient as any other method > people had come up with. > > Ed > > Here’s a reference from 1986 that I think was based on paper at a > Bellman Continuum > > ``From Dynamic Programming to Fast Transforms,'' E. Angel, J. > Math. > Anal. Appl.,119,1986. > > Ed > __________ > > Ed Angel > > Founding Director, Art, Research, Technology and Science > Laboratory > (ARTS Lab) > Professor Emeritus of Computer Science, University of New Mexico > > 1017 Sierra Pinon > Santa Fe, NM 87501 > 505-984-0136 (home) edward.an...@gmail.com > 505-453-4944 (cell) http://www.cs.unm.edu/~angel > > > On Apr 28, 2023, at 8:18 AM, Stephen Guerin < > stephen.gue...@simtable.com> wrote: > > Special Unitary Groups and Quaternions > > Mostly for Ed from the context of last week's Physical Friam > if > you're coming today. > > Discussion was around potential ways of visualizing the > dynamics of SU(3), SU(2), (SU1) that highlights Special > Unitary > Groups. (wiki link from Frank), and can we foreground how > quaternions are used in this process. > > and a related bit on forces, I'm searching for ways to > visualize/understand how FFTs with Poisson equation are used > to > compute the forces from scalar fields (eg gravitational force > from mass density, electric force from charge, etc) and if > there's any relation to Special Unitary Groups. > > -S > -. --- - / ...- .- .-.. .. -.. / -- --- .-. ... . / -.-. --- > -.. . > FRIAM Applied Complexity Group listserv > Fridays 9a-12p Friday St. Johns Cafe / Thursdays 9a-12p > Zoom https://bit.ly/virtualfriam > to (un)subscribe http://redfish.com/mailman/listinfo/ > friam_redfish.com > FRIAM-COMIC http://friam-comic.blogspot.com/ > archives: 5/2017 thru present https://redfish.com/pipermail/ > friam_redfish.com/ > 1/2003 thru 6/2021 http://friam.383.s1.nabble.com/ > > > -. --- - / ...- .- .-.. .. -.. / -- --- .-. ... . / -.-. --- -.. . > FRIAM Applied Complexity Group listserv > Fridays 9a-12p Friday St. Johns Cafe / Thursdays 9a-12p Zoom > https://bit.ly/virtualfriam > to (un)subscribe http://redfish.com/mailman/listinfo/ > friam_redfish.com > FRIAM-COMIC http://friam-comic.blogspot.com/ > archives: 5/2017 thru present https://redfish.com/pipermail/ > friam_redfish.com/ > 1/2003 thru 6/2021 http://friam.383.s1.nabble.com/ > > -. --- - / ...- .- .-.. .. -.. / -- --- .-. ... . / -.-. --- -.. . > FRIAM Applied Complexity Group listserv > Fridays 9a-12p Friday St. Johns Cafe / Thursdays 9a-12p Zoom > https: > //bit.ly/virtualfriam > to (un)subscribe http://redfish.com/mailman/listinfo/friam_redfish.com > FRIAM-COMIC http://friam-comic.blogspot.com/ > archives: 5/2017 thru present https://redfish.com/pipermail/ > friam_redfish.com/ > 1/2003 thru 6/2021 http://friam.383.s1.nabble.com/ > > > -. --- - / ...- .- .-.. .. -.. / -- --- .-. ... . / -.-. --- -.. . > FRIAM Applied Complexity Group listserv > Fridays 9a-12p Friday St. Johns Cafe / Thursdays 9a-12p Zoom https:// > bit.ly/virtualfriam > to (un)subscribe http://redfish.com/mailman/listinfo/friam_redfish.com > FRIAM-COMIC http://friam-comic.blogspot.com/ > archives: 5/2017 thru present https://redfish.com/pipermail/ > friam_redfish.com/ > 1/2003 thru 6/2021 http://friam.383.s1.nabble.com/ > > -. --- - / ...- .- .-.. .. -.. / -- --- .-. ... . / -.-. --- -.. . > FRIAM Applied Complexity Group listserv > Fridays 9a-12p Friday St. Johns Cafe / Thursdays 9a-12p Zoom > https://bit.ly/virtualfriam > to (un)subscribe http://redfish.com/mailman/listinfo/friam_redfish.com > FRIAM-COMIC http://friam-comic.blogspot.com/ > archives: 5/2017 thru present > https://redfish.com/pipermail/friam_redfish.com/ > 1/2003 thru 6/2021 http://friam.383.s1.nabble.com/ -- ---------------------------------------------------------------------------- Dr Russell Standish Phone 0425 253119 (mobile) Principal, High Performance Coders hpco...@hpcoders.com.au http://www.hpcoders.com.au ---------------------------------------------------------------------------- -. --- - / ...- .- .-.. .. -.. / -- --- .-. ... . / -.-. --- -.. . FRIAM Applied Complexity Group listserv Fridays 9a-12p Friday St. Johns Cafe / Thursdays 9a-12p Zoom https://bit.ly/virtualfriam to (un)subscribe http://redfish.com/mailman/listinfo/friam_redfish.com FRIAM-COMIC http://friam-comic.blogspot.com/ archives: 5/2017 thru present https://redfish.com/pipermail/friam_redfish.com/ 1/2003 thru 6/2021 http://friam.383.s1.nabble.com/
