How beatiful is this stuff on matrixes and graphs ?

Yes I know that graphs are represented by incidence and adiacency matrixes. However I never realize how a matrix can be represented by bipartite (or multipartite graphs). My attention was brought to it by the Math3ma blog (by Tai Danae Bradley) which I follow with delight (I am not saying that I am understanding all I read there). In particular this blog post entitles "Viewing matrices and probability as graphs".

The figure above comes from that blog and explain the concept that a matrix can be represented by a bipartite graph. If you understand it, then you can click on the Figure and continue your reading at the original blog.
After that, I noticed that the matrix representation is actually quite concise. Is it the minimal (using less numbers, excluding indexes) representation of the graph ? And, viceversa, given a graph, can we partitions its nodes in  sets such that any node in a group is connected with nodes in the other groups, but not with those in the same group ? If we are able to do so, we can subsequently build the matrix representation of the graph, reverting the process used in figure. If our set of nodes in the graph is tripartite, then the resulting matrix will be three-dimensional and so on.

In 1D (on the line) the partition is obvious and  is a bi-partition.  In 2D, the problem seems to be necessary a qudri-partition, at least for those graphs that are grids (cw-complexes): in fact the problem is the same of that brought to the four color problem. What happens in 3D ?

P.S. - Recently (2019-07-16)I found this interesting paper.

A smooth introduction to some Algebraic Topology topics

Since the previous post on Grids touched some topics on algebraic topology, I  selected a few sites where I found some interesting information from our point of view that can help the reading of the previous slides and, in general, of the references already presented.

• This science4all site is a very visual and simple introduction to most of the concepts formalized in slides.
• Isabel Darcy's video lectures  on Applied Algebraic Topology are also enjoyable (You can stop anywhere but I put them all)
• On Euler's characteristics (We did not mention it in slides, but is worth to know)
• Simplicial, Addition, Orientation
• Modular Mathematics
• Addition and free vector spaces
• Triangulation and simplicial complexes
• Creating a simplicial complex from data 
• Persistent Homology  - I
• Persistent Homology - II
• Persistent Homology - III 
• A quick example calculating the column space and the nullspace of a matrix
•  Clustering via persistent Homology

 

• Enzo Tonti's lectures about his book

• The reasons of analogies in Physics - Part I - Part II - Part III - Part IV - Part V - Part VI

I do not share many of Tonti's opinions, but some of his talks and books are, indeed, enlightening.

Meshes, Grids, CW-Complexes

Representation of space (and time) is a necessary step to implement any Physics. However, the topic is seldom faced with the appropriate generality, and this reflects into implementations in softwares that do not have a general structure. This is the rational for talking here about meshes or grids.
From a quick view of the material found in literature, it appears that a lot of work has been done, by few people (group). There are at least two pathways to follow. The first is the Ugrid mesh specification. We can describe it as the classification work of mesh by power users, i.e. people who use meshes for describing (especially environmental) numerical problems. Their work is concentrated on semantics and explaining what the mesh are,  with the scope to insert them in NetCDF, a self explaining file format conceived to contain environmental data.
The second approach, in Berti (2000) starts from more fundamental mathematical work which is also used in Heinzl (2007, but referring to the paper Heinzl, 2011, could be convenient).
In general, the first two chapters of Berti’s dissertation are a must-to-read for those who deals with scientific computing.
A subsequent number of papers cover two topics: how to store mesh in databases and how to give to these structures the right flexibility to be parallelized. Interestingly some of the mathematical work actually flowed into the creation of C++ libraries, in particular the GRAL libraries, developed by Berti himself.

Browsing around, mesh are rigorously defined in Algebraic Topology (e.g. Hatcher, 2001) and this was  recognized in various papers, since the sixties (e.g. Branin, 1966, and references therein). A general discussion, which involve the nature of Physical laws, was produced by Tonti (2013) and somewhat pushed also by Ferretti (2015).  These treatments could bring in the matter some new insight and the general understanding. What we did with the slides was to try to synthetize some of the above work, especially in view of an implementation of some Java libraries. The idea suggested by the readings was to use generic programming, design patters (Gamma et al, 1994, Freeman et al., 2005) and programming to interfaces (which BTW we already have in mund: we found what we were looking for). 
But the detail of the implementation will be the topic of a future post (but you can have a glance to literature browsing the bibliography below). Now get (a little of) theories by clicking on the figure above.

References

• Berti, G. (2000, May 25). Generic Software Components for Scientific Computing.
• Branin, F. H. (1966). The algebraic-topological basis for network analogies and the vector calculus (pp. 1–40). Presented at the Symposium on generalized Networks, New York.
• Ferretti, E. (2015). The algebraic formulation: why and how to use it. Curved and Layer. Struct., 2, 106–149. http://doi.org/10.1515/cls-2015-0007
• Gamma, E., Helm, R., Johnson, R., & Vlissides, J. (1994). Design Patterns Elements of Reusable Object-Oriented Software (pp. 1–417). Addison-Wesley.
• Hatcher, A. (2001), Algebraic Topology. 
• Freeman, Eric, Freeman, E., Sierra, K., & Bates, B. (2004). Head First Design Patterns (pp. 1–672). O'Reilly.
• Heinzl, R., & Schwaha, P. (2011). A generic topology library. Science of Computer Programming, 76(4), 324–346. http://doi.org/10.1016/j.scico.2009.09.007
• Naftalin, M., & Wader, P. (2009). Java Generics and Collections (pp. 1–286). O'Reilly.
• Nikishkov, G. (2006). Object oriented design of a finite element code in Java. Cmes, 11, 81–90. http://doi.org/10.3970/cmes.2006.011.081
• Nikishkov, G. (2010). Programming Finite Elements in Java (pp. 1–394). Springer-Verlag 2010.
• Simonelli, C. (2015, November 22). Programmazione parallela strutturata in Java8: Muskel2. (M. Danelutto, Ed.).
• Tonti, E. (2013). The Mathematical Structure of Classical and Relativistic Physics (pp. 1–537).  

Notes

Some of my  students asked for somewhat a milder introduction to algebraic  topology.  I dedicated a new short post to it.