THE CALCULUS OF FINITE DIFFERENCES

By WILLIAM ROBINSON

CONTENTS DISCRETE CALCULUS: HISTORY AND FUTURE DISCRETE CALCULUS ORIGINS OF VECTOR CALCULUS ORIGINS OF DISCRETE CALCULUS DISCRETE VS DISCRETIZED COMPLEX NETWORKS CONTENT EXTRACTION ORGANIZATION OF THE BOOK INTENDED AUDIENCE PART I A BRIEF REVIEW OF DISCRETE CALCULUS INTRODUCTION TO DISCRETE CALCULUS TOPOLOGY AND THE FUNDAMENTAL THEOREM OF CALCULUS DIFFERENTIAL FORMS EXTERIOR ALGEBRA AND ANTISYMMETRIC TENSORS DIFFERENTIATION AND INTEGRATION OF FORMS THE HODGE STAR OPERATOR DIFFERENTIAL FORMS AND LINEAR PAIRINGS DISCRETE DOMAINS DISCRETE FORMS AND THE COBOUNDARY OPERATOR PRIMAL AND DUAL COMPLEXES THE ROLE OF A METRIC: THE METRIC TENSOR, THE DISCRETE HODGE STAR OPERATOR, AND WEIGHTED COMPLEXES THE DUAL COBOUNDARY OPERATOR THE DISCRETE LAPLACE–DE RHAM OPERATOR STRUCTURE OF DISCRETE PHYSICAL LAWS EXAMPLES OF DISCRETE CALCULUS FUNDAMENTAL THEOREM OF CALCULUS AND THE GENERALIZED STOKES’ THEOREM THE HELMHOLTZ DECOMPOSITION MATRIX REPRESENTATION OF DISCRETE CALCULUS IDENTITIES ELLIPTIC EQUATIONS DIFFUSION ADVECTION CONCLUDING REMARKS CIRCUIT THEORY AND OTHER DISCRETE PHYSICAL MODELS CIRCUIT LAWS STEADY-STATE SOLUTIONS DEPENDENT SOURCES ENERGY MINIMIZATION AC CIRCUITS CONNECTIONS BETWEEN CIRCUIT THEORY AND OTHER DISCRETE DOMAINS SPRING NETWORKS RANDOM WALKS GAUSSIAN MARKOV RANDOM FIELDS TREE COUNTING LINEAR ALGEBRA APPLIED TO CIRCUIT ANALYSIS CONCLUSION PART II APPLICATIONS OF DISCRETE CALCULUS BUILDING A WEIGHTED COMPLEX FROM DATA DETERMINING EDGES AND CYCLES DE?NING AN EDGE SET DE?NING A CYCLE SET DERIVING EDGE WEIGHTS EDGE WEIGHTS TO RE?ECT GEOMETRY EDGE WEIGHTS TO PENALIZE DATA OUTLIERS EDGE WEIGHTS TO CAUSE REPULSION EDGE WEIGHTS TO REPRESENT JOINT STATISTICS DEDUCING EDGE WEIGHTS FROM OBSERVATIONS OBTAINING HIGHER-ORDER WEIGHTS TO PENALIZE OUTLIERS WEIGHTS BEYOND FLOWS METRICS DE?NED ON A COMPLEX FILTERING ON GRAPHS FOURIER AND SPECTRAL FILTERING ON A GRAPH GRAPHS THAT ARE NOT SHIFT-INVARIANT THE ORIGINS OF HIGH FREQUENCY NOISE ENERGY MINIMIZATION METHODS FOR FILTERING THE BASIC ENERGY MINIMIZATION MODEL EXTENDED BASIC ENERGY MODEL THE TOTAL VARIATION MODEL FILTERING WITH IMPLICIT DISCONTINUITIES FILTERING WITH EXPLICIT, BUT UNKNOWN, DISCONTINUITIES FILTERING BY GRADIENT MANIPULATION NONLOCAL FILTERING FILTERING VECTORS AND FLOWS TRANSLATING SCALAR FILTERING TO FLOW FILTERING FILTERING HIGHER-ORDER COCHAINS APPLICATIONS IMAGE PROCESSING THREE-DIMENSIONAL MESH FILTERING FILTERING DATA ON A SURFACE GEOSPATIAL DATA FILTERING FLOW DATA—BRAIN CONNECTIVITY 5 10 CONCLUSION CLUSTERING AND SEGMENTATION TARGETED CLUSTERING PRIMAL TARGETED CLUSTERING DUAL TARGETED CLUSTERING UNTARGETED CLUSTERING PRIMAL UNTARGETED CLUSTERING DUAL UNTARGETED CLUSTERING SEMI-TARGETED CLUSTERING THE K-MEANS MODEL CLUSTERING HIGHER-ORDER CELLS CLUSTERING EDGES IMAGE SEGMENTATION SOCIAL NETWORKS MACHINE LEARNING AND CLASSI?CATION GENE EXPRESSION MANIFOLD LEARNING AND RANKING MANIFOLD LEARNING MULTIDIMENSIONAL SCALING AND ISOMAP LAPLACIAN EIGENMAPS AND SPECTRAL COORDINATES LOCALITY PRESERVING PROJECTIONS RELATIONSHIP TO CLUSTERING MANIFOLD LEARNING ON EDGE DATA RANKING PAGERANK HITS SHAPE CHARACTERIZATION POINT CORRESPONDENCE WEB SEARCH JUDICIAL CITATION MEASURING NETWORKS MEASURES OF GRAPH CONNECTEDNESS GRAPH DISTANCE NODE CENTRALITY DISTANCE-BASED PROPERTIES OF A GRAPH MEASURES OF GRAPH SEPARABILITY CLUSTERING MEASURES SMALL-WORLD GRAPHS TOPOLOGICAL MEASURES GEOMETRIC MEASURES DISCRETE GAUSSIAN CURVATURE DISCRETE MEAN CURVATURE CHEMICAL GRAPH THEORY CHAPTER DISCRETE CALCULUS: HISTORY AND FUTURE ABSTRACT THE GOAL OF THIS BOOK IS TO BRING TOGETHER THREE ACTIVE AREAS OF CURRENT RESEARCH INTO A SINGLE FRAMEWORK AND SHOW HOW EACH AREA BENE?TS FROM MORE EX- POSURE TO THE OTHER TWO THE AREAS ARE: DISCRETE CALCULUS, COMPLEX NETWORKS, AND ALGORITHMIC CONTENT EXTRACTION ALTHOUGH THERE HAVE BEEN A FEW INTERSECTIONS IN THE LITERATURE BETWEEN THESE AREAS, THEY HAVE LARGELY DEVELOPED INDEPENDENTLY OF ONE AN- OTHER HOWEVER, WE BELIEVE THAT RESEARCHERS WORKING IN ANY ONE OF THESE THREE AREAS CAN STRONGLY BENE?T FROM THE TOOLS AND TECHNIQUES BEING DEVELOPED IN THE OTHERS WE BEGIN THIS BOOK BY OUTLINING EACH OF THESE THREE AREAS, THEIR HISTORY AND THEIR RELATIONSHIP TO ONE ANOTHER SUBSEQUENTLY, WE OUTLINE THE STRUCTURE OF THIS WORK AND HELP THE READER NAVIGATE ITS CONTENTS 1 1 DISCRETE CALCULUS THE TERM “DISCRETE CALCULUS” IS ONE OF MANY EXPRESSIONS, ALONG WITH “DISCRETE EX- TERIOR CALCULUS” AND “MIMETIC DISCRETIZATION”, THAT DESCRIBES THE BODY OF LITERATURE THAT HAS FOCUSED ON ?NDING A PROPER SET OF DE?NITIONS AND DIFFERENTIAL OPERATORS THAT MAKES IT POSSIBLE TO OPERATE THE MACHINERY OF MULTIVARIATE CALCULUS ON A ?NITE, DIS- CRETE SPACE IN CONTRAST TO TRADITIONAL GOALS OF ?NDING AN ACCURATE DISCRETIZATION OF CONVENTIONAL MULTIVARIATE CALCULUS, DISCRETE CALCULUS ESTABLISHES A SEPARATE, EQUIV- ALENT CALCULUS THAT OPERATES PURELY IN THE DISCRETE SPACE WITHOUT ANY REFERENCE TO AN UNDERLYING CONTINUOUS PROCESS THEREFORE, THE PURPOSE OF THIS ?ELD HAS BEEN TO ESTABLISH A FULLY DISCRETE CALCULUS RATHER THAN A DISCRETIZED CALCULUS THE STANDARD SETTING FOR THIS DISCRETE CALCULUS IS A CELL COMPLEX, OF WHICH A GRAPH OR NETWORK IS A SPECIAL CASE ALTHOUGH THE TOOLS OF DISCRETE CALCULUS HAVE RISEN TO PROMINENCE MORE RECENTLY, THE CONCEPTS IN DISCRETE CALCULUS WERE HISTORICALLY DEVELOPED IN PARALLEL WITH THE CONVENTIONAL CALCULUS IN FACT, THE ORIGINS OF BOTH CONVENTIONAL VECTOR CALCULUS AND DISCRETE CALCULUS HAVE THEIR ORIGINS IN STUDIES OF SPATIAL REPRESENTATIONS AND RELATION- SHIPS AS WELL AS THE DESCRIPTION OF PHYSICAL SYSTEMS ASSOCIATED WITH SPACE IN ORDER TO UNDERSTAND THE RELATIONSHIP OF CONVENTIONAL CALCULUS TO DISCRETE CALCULUS, WE BELIEVE THAT IT IS USEFUL TO BRIE?Y EXAMINE THE HISTORY OF DEVELOPMENT IN BOTH AREAS