Here are just some codes as I write them. These are of course not at
all yet complete. The codes are written in FWEB,
a macro preprocessor/pretty printer for Fortran and C. This is somewhat
complicated package, but it makes nice documentation which you can find
below (just sample F90 codes).
I am leaving MSU in August of 2001 to attend Princeton University. I
will likely continue working on SSCNO, starting to think about parallelization.
At present these codes are not finished enough to release them as a packaged
library. But you are free to download and look at the codes individually.
Please note that eventually these will be released under the GNU GPL licence
and I am their original author. Please let me know if you have downloaded
these codes and used them inside yours!

Module Precision
This is just a module with parameter kinds and is used by all codes.
Here is the web file, PDF
documentation (also dvi) and source
code.

Random Number Generation, module RandomNumbers
The web file RandomDistributions.web
contains the source for a library that generates random numbers drawn from
a uniform or gaussian distribution. It is very portable and uses a fast
shiftbased generator. Here is the produced PDF
documentation (also dvi) and
the produced Fortran 90 source code.
If you need this file for another architecture and do not wanna install
and learn how to use FWEB
(though I recommend this!), then just email
me. More distributions need to be added here!

Scientific and Network Plotting
The functions in the module Simple_Graphics are similar to
the ones documented in the PHY201
SimpleGraphics page, but they have been improved and only
plot two dimensional plots with vector x and y data, so the
user has more freedom but also more responsibilities. This will be used
to plot things like convergence or scaling. It is based on the DISLIN
library. Here is the web file, the produced
Fortran source code and the produced documentation
(also dvi). Here is a sample
file that uses it, and the produced plot.
The functions in the module Network_Graphics are a specialization
of the ones in SimpleGraphics for plotting planar graphs with
specified values at the nodes and/or arcs. It is rather niffty, I think.
Here is the web file, the documentation
(also dvi) and the source
code. Here is a simple file that uses it
(this uses random number generation and thus generates a graph that is
not really planar) and the produced plot.
Some of the results shown below are produced with this library and illustrate
its power.

Sorting and Ranking, module Sorting_Ranking,
and Search Skip Lists, module Skip_Lists
The following library implements several sorting algorithms to rank
numerical arrays. Here is the web file, the produced
Fortran code (also the used error
function codes), the documentation (also
dvi). Here are two files that test this library
(web, Fortran,
documentation (dvi))
and time the various sorts for real arrays of various size and of variable
initial "sortedness" (web, Fortran,
documentation (dvi)).
The results of the timing on my machine showing which
sort is the fastest are here, and here are the best
ranking times.
Also in this group of algorithms I may include something I worked on
for my CSE890 coursean implementation of skip lists, a very efficient
probabilistic selfbalanced data structure (web,
Fortran, documentation
(dvi)).

System Utilities, modules Error_Handling,
System_Monitors, Initialization_Termination
These modules deal with some things such as timing, exception handling,
allocation monitoring, etc. Here is the web file
for the exceptionhandling module Error_Handling, the source
code and the documentation (also dvi).
Here is the web file for System_Monitors,
the source code and documentation
(dvi). And finally the web
file for Initialization_Termination, the produced source
code and documentation (dvi).
These can be upgraded beyond standard Fortran on other architectures and
compilers.

Combinatorial Algorithms, module Graph_Algorithms
and module Network_Spanning_Trees, and module Network_Matrix_Operations
This is an almost finished file (web, Fortran,
documentation (dvi)),
for now it calculates connectedcomponents labels for a graph and also
has routines for building and maintaining minimal spanning trees (MSTs),
and I also finished coding a backbone extraction algorithm in the same
spirit as these. It also contains other scattered graph algorithms. This
is a huge filethe documentation is 45 pages! It needs to be split into
pieces...Also take a look at this interface to some FORTRAN 77 graph
codes from NETLIB which I adopted to Fortran 90 (Fortran
code) in Graph_Algorithms_F77 (web,
Fortran, documentation
(dvi)).
Here is the module Network_Spanning_Trees, which is a frontend
interface to the lowerlevel routines in Graph_Algorithms (web,
Fortran, documentation
(dvi)). Here is an illustration of the algorithm
that extracts the backbone in forms of cute images (a lattice network with
the largest connectedcluster
extracted, and with the largest
backbone cluster extracted, as well as a colored graph showing the
difference in the two (the dangling ends)).
Here is an example program that times these routines for building and maintaining
MSTs (web, Fortran,
documentation (dvi)).
Here is the main result of this timing (plots of tree building time for
different sizes of the graphs and different
perturbations to the weights) showing the relative superiority of the
updateroutines based on cycle traces. And here is just a sample program
that makes cute plots the MSTs with colors for depth and cardinalities
for the tree arcs and the tree nodes (web, Fortran,
documentation (dvi)),
along with the plots (node depths
and arc cardinalities for 50x50 lattice).
In this category, at least for now, I should include the routines that
perform some linear algebra on network arrays (web,
Fortran, documentation
(dvi)).

NearNeighbor Lattices, modules Network_Data_Structures,
Lattice_Geometry, Network_Geometry and Space_Filling_Curves
These sophisticated modules deal with setting up a network optimization
problem based on a nearneighbour lattice geometry. The module Network_Data_Structures
contains in it some shard commonly used arrays (web,
Fortran, documentation
(dvi)). The module Lattice_Geometry
actually sets up a network with a desired geometry (web,
Fortran, documentation
(dvi)) and the module Network_Geometry
finishes the job by creating a network out of the lattice (web,
Fortran, documentation
(dvi)). Here is an example input
options file for a 2D network and severalIMAGES
[ 2D Network (geometrical status
identifiers, nodal suppliesdemands
and resistances of arcs, triangular
lattice), 3D Network (geometrical
status, suppliesdemands and
resistances] produced with Network_Graphics using the
following main program (web, documentation
(dvi)). This module also does computation
and data reordering based on the module Space_Filling_Curves (C
source code for SFC
library from DASCI project, web, Fortran,
documentation (dvi), Hilbert
SFC nodeordering, Morton SFC
nodeordering).

Elemental Cost Functiona, modules
Power_Cost_Parameters , FF_Cost_Parameters and Power_Cost_Functions,
FF_Cost_Functions
These modules are the ones that should change when changing the cost
function. However, they are prototypes that should be used as models when
trying to rewrite them for a new cost function. I have provided two examples
here, a powerlaw cost function and a cost function suitable for certain
types of superconductors (FluxFlow). Here is the module that sets up the
random cost parameters for the arcs for powerlaw costs (web,
Fortran, documentation
(dvi)) and for FF(web,
Fortran, documentation
(dvi)), and the module that calculates the derivatives
(and some inverses) of the elemental cost functions for powerlaw (web,
Fortran, documentation
(dvi)) and FF cost functions (web,
Fortran, documentation
(dvi)). We have several other functions
we use, but they all follow the same design principle. Their main characteristic
is transientlike behaviour near a cricial flow (current) or tension (voltage),
as shown in this regularization illustration.

Using LSNNO, modules Lattice_Network_Optimization
and LSNNO_Interface
The module Lattice_Network_Optimization is just a frontend
interace to the many routines above for easeofuse (web,
Fortran, documentation
(dvi)). LSNNO
(Large Scale Nonlinear Network Optimization) is the only publicdomain
network optimization library today (soon to be replaced with my library
LSCNO). The first step in this project was to get this library working
with our networks, to be used for validation and comparision later on.
This is done in the module LSNNO_Interface (web,
Fortran, documentation
(dvi)). I am happy to say this endevour was successful
:), albeit after some considerable trouble. Here is a test program that
runs LSNNO for a network with powerlaw costs (web,
Fortran, documentation
(dvi)) and the first sample results it produced (Flow
pattern, Potential pattern)

Solving dual Newton systems, modules Network_Data_Types
and Conjugate_Gradient, Vector_Operations, TAUCS_Interface,
SCOTCH_Interface, CHACO_Interface and Dual_Newton_Solvers
The module Conjugate_Gradient implements a PCG iterative linear
solver (web, Fortran,
documentation (dvi))
to be used in solving Newton's system of equations later on. Its design
is based on the objectoriented framework of Fortran 2002 and is explained
in my two papers for the Fortran Forum dealing with reverse
communication and iterative linear solvers.
In order to avoid aliasing optimization problems with array pointers (used
extensively in SSCNO), I designed a set of vector operation routines in
the module Vector_Operations (web, Fortran,
documentation (dvi)).
I also provide direct solvers based on Cholesky factorization (these
work great in 2D), mostly via interfacing to some publicdomain libraries,
such as the factorization library TAUCS
of Sivan Toledo (web, Fortran,
documentation (dvi)), the
graph partitioning and matrix reordering library SCOTCH
of Francois Pellegrini (web, Fortran,
documentation (dvi)),
as well as the graph partitioning library CHACO
of Bruce Hendrickson et al. (web, Fortran,
documentation (dvi)). Please
note that I made some minor changes to the sources of all these libraries.
As they themselves are changing, there is no purpose in putting these patches
here...
PCG and Cholesky factorization are used in the module that implements
the dual solvers Dual_Newton_Solvers (web,
Fortran, documentation
(dvi)), which uses the preliminary version
of network derived datatypes (which I avoided so far...), Network_Data_Types
(web, Fortran,
documentation (dvi)).
Here is an example program that times and tests different preconditioners
for the dual systems (Outdated: web,
Fortran, documentation
(dvi)). Most of these are supportgraph
preconditioners, and some comments about them can be found in my report
on preconditioning Laplacian systems.
The codes that manipulate regular (i.e. fixed height and fixeddegree)
support trees are in the module Support_Trees (web,
Fortran, documentation
(dvi)).

Newton algorithms implemented in SSCNO, modules
Dual_Line_Search and Dual_SSCNO, and SSCNO_Interface
The module Dual_Line_Search implements some line search procedures
for minimizing the lagrangian or dual Lagrangian for a strictly convex
network optimization problem in either flow or potential space (web,
Fortran, documentation
(dvi)).
The toplevel of SSCNO at present is the module Dual_SSCNO
(web, Fortran,
documentation (dvi))
which implements two second order algorithms, the Truncated Dual Newton
(TDN) and the Truncated Sequential Quadratic Programming (TSQP) algorithms,
described in a more condensed form in this code extraction (web,
documentation (dvi)).
The system of derived datatypes (i.e. class containers) within SSCNO is
somewhat scanty, but is summarized in this code extraction (web,
documentation (dvi)).
The interface between SSCNO and the hypercube lattice generation routines
is given in the module SSCNO_Interface (web,
Fortran, documentation
(dvi)).

Using SSCNO in materials science. Programs IV,
Breakdown and Saturation.
But
of course it is far from finished (and it may never be). It is exciting
to introduce the advances of convex optimization to the materialsscience
community, which is behind on basic optimization theory. A paper is currently
in preparation with details.
Here is the program IV (web, Fortran,
documentation (dvi)) which plots
voltagecurrent characterstics of networks. Here is an IV
curve of a 100 by 100 2D sample model for a granular superconductor.
Corey Musolffc is working on using this program to collect numerically
averaged data of this sort.
Even more exciting are cases in which critical
breakdowns and saturations of the voltage or flow occur along combinatorial
structures. The program Breakdown (web,
Fortran, documentation
(dvi)) models varistor materials and compares
the breakdown paths with shortest paths (Dijkstra's
tree, small currents, near
critical voltage, larger currents).
The program Saturation (web, Fortran,
documentation (dvi))
models the onset of disippation via flow saturation in superconducting
materials and compares it against maxflow/mincut combinatorial structures
(recursive ST minimal cuts,
small voltage, near
critical current, larger voltage).
There is plenty of physics and applied mathematics (in regularization approaches,
preconditioning, and using combinatorial structures as initial guesses)
here, and you will see more on this page soon enough :)