George W. Hart

george@georgehart.com


Selected Recent Publications

Research Summary

My recent work is centered on sculpture, the history of geometry in art, and computational geometry of polyhedra (see recent publications above).  Several areas of my past research are briefly summarized below, and pointers to further information are given:
  1. Multidimensional Analysis
  2. Nonintrusive Appliance Load Monitoring
  3. Telecommunications Network Management
  4. Viterbi Algorithm Extensions
  5. Recreational Cryptography
  6. Multimedia Polyhedra for the WWW
From the mathematical perspective of detection and estimation theory and algorithms, these topics are all closely intertwined.

1. Multidimensional Analysis

The study of ``dimensioned quantities," such as 1 volt, and 2 meters, and their possible interrelationships, forms an interesting branch of applied mathematics (or physics or engineering) called dimensional analysis. Traditionally this field only concerns scalar quantities (not vectors and matrices).

The linear algebra which results when one considers vectors and matrices which contain dimensioned quantities as their components is surprisingly interesting and rich. Although it is implicit in all branches of modern engineering, it has not been carefully studied before.

For an introduction to dimensioned linear algebra and the dimensional analysis of matrix relationships, be sure to check out my Multidimensional Analysis page, and check out my book, which assumes an undergraduate background in linear algebra:

George W. Hart, Multidimensional Analysis: Algebras and Systems for Science and Engineering, Springer Verlag, 1995.

Software for Scalars:

A very useful computer program (which I have written and placed in the public domain) for manipulating, converting, and calculating with dimensioned scalars is available by anonymous FTP from many places, including my FTP directory and SimTel and Garbo. The program, DimCalc, runs under Windows on PC compatibles and other machines which run Microsoft Windows 3.1 or higher software. The file to get is DimCalc.zip which is a compressed package of the software and extensive on-line help information. Also get the vbrun300.dll subroutine file if you do not have it on your system already.
 

2. Nonintrusive Appliance Load Monitoring

A Nonintrusive Appliance Load Monitor determines the energy consumption of individual appliances turning on and off in an electric load, based on detailed analysis of the current and voltage of the total load, as measured at the interface to the power source. The approach has been developed to simplify the collection of residential energy consumption data by utilities, but also has other applications. It is called nonintrusive to contrast it with previous techniques for gathering appliance load data, which require placing sensors on individual appliances, and hence an intrusion onto the energy consumer's property.

An interesting aspect of this research is the interdisciplinary manner in which it combines power systems theory and communications theory---power consumption is decoded as an act of information transfer. The theory and current practice of Nonintrusive Appliance Load Monitoring, including goals, applications, load models, appliance signatures, algorithms, prototypes, field-test results, current research directions, and the advantages and disadvantages of this approach relative to intrusive monitoring are described in the following tutorial survey article:

G. Hart, ``Nonintrusive Appliance Load Monitoring," IEEE Proceedings, December 1992, pp. 1870-1891.

For additional on-line information, be sure to explore my Nonintrusive Appliance Load Monitoring Page.
 

3. Telecommunication Network Management

Telecommunication networks (such as the Internet), because of their complexity and dynamics, are subject to many kinds of difficult-to-deal-with faults. Important fault management issues include the detection, localization, description, identification, and work-around of both hardware and software faults.

Research results related to all these fault management problems are described in a number of papers listed in the references below. Look for the papers joint authored by me and any of the following ex-Ph.D. students from the Columbia University Center for Telecommunications Research: Samir Kelekar, Isabelle Rouvellou, Jean-Francois Labourdette, and Anastasios Bouloutas.
 

4. Viterbi Algorithm Extensions

A new channel model and ``Channel Inversion Algorithm" have been developed for correcting symbol sequences that have been corrupted by an unknown combination of known fault mechanisms. The algorithm is similar to the Viterbi algorithm in that it is suitable for situations where the uncorrupted data string is generated by a known finite-state process, but it is more versatile in that it can correct a much broader class of errors. Of particular importance is the fact that our algorithm corrects common context-sensitive errors, such as symbol changes, transpositions, mergers, splits, insertions, and deletions, which may be assigned different probabilities depending on the context of preceding and/or subsequent symbols. As many communication channels can be modeled in this way, this new algorithm is a significant extension over the Viterbi Algorithm and previous decoding techniques. It has many applications in such diverse fields as channel coding, pattern recognition, and estimation for discrete-event systems, whenever one has finite-state models and noisy data.

This channel inversion algorithm can be understood in terms of a ``quasi-trellis," related to the trellis of the Viterbi Algorithm; it contains the same number of states, with a quasi-regular collection of arcs corresponding to user-specified types of context-dependent errors. We introduce the notion of ``channel rules" to provide a framework for the user to specify the channel operation. The algorithm is given in both an ``off-line'' form and a ``recursive'' form suitable for sequentially presented data streams. In most applications, the recursive form has computational complexity only a constant times that of the Viterbi Algorithm.

This research is joint work with Dr. Anastasios Bouloutas of IBM T.J. Watson Research Laboratories. For detailed information, see our paper Correcting Dependent Errors in Sequences Generated by Finite-State Processes,listed below, and references therein.
 

5. Recreational Cryptography

Short cryptograms, in which an encoded sentence or quotation is to be decoded, are common pastimes of many recreational puzzle enthusiasts. Here is a simple example of the type that can be found in many collections of word games, and daily in some newspapers: 
Given (cipher text):    YP NR, PT MPY YP NR: YJSY OD YJR WIRDYOPM.
Solution (plain text):  TO BE, OR NOT TO BE: THAT IS THE QUESTION.
A permutation of the 26-character alphabet is used to encode a sentence, leaving spacing and punctuation intact. Given only the encoded sentence (the cipher text), the correct permutation is to be found so that the original sentence (the plain text) can be understood.

Cryptograms of this form--simple permutation substitutions with word divisions--have been employed for message concealment at least since Roman times. The solution of simple permutation ciphers has not been of much practical importance since their use for military communication was superseded in the nineteenth century, but they remain a formidable puzzle for those who enjoy word games. Experienced solvers can manually solve a typical one-sentence cryptogram in a few minutes, but carefully constructed short puzzles, with unusual letter frequencies or atypical letter combinations, can stymie even expert solvers.

A simple algorithm for deciphering cryptograms is described in the following reference:

G. Hart, ``To Decode Short Cryptograms," Communications of the ACM, Sept., 1994, pp. 102-108.

The C source code for the program described there is available.

6. Multimedia Polyhedra for the Web

Polyhedra are fundamental geometrical objects which have important applications a great variety of fields. To fully appreciate their beauty and mathematical properties, one must have three-dimensional models which one can spin about and observe from different perspectives. Previously, paper models were the only convenient means for most people to learn about polyhedra. Being laborious-to-construct physical objects, they have many limitations. For example, they can only be in one place at a time. With the advent of virtual reality modelling over the internet, now everyone everywhere can explore the beauty and mathematical elegance of three-dimensional polyhedra models through their web browser. I am constructing an Encyclopedia of Polyhedra with hundreds of 3D models which you can examine, spin, and even fly inside of.