Institute for Computational Mathematics

List of recent publications



Here is a list of the main publications since 1994.

Journal articles

    1994
  1. A. Bernasconi, M. Leoncini, and G. Resta, Spectral Properties of Some Matrices Close to the Toeplitz Triangular Form, Computers and Mathematics with Applications, 27, 79-92 (1994)
  2. B. Codenotti, M. Leoncini, and G.Resta, Oracle Computations in Parallel Numerical Linear Algebra, Theoretical Computer Science, 127, 99-121 (1994)
  3. P. Favati, G. Lotti, and F. Romani, Theoretical and Practical Efficiency Measures for Symmetric Interpolatory Quadrature Formulas, BIT, 34, 546-557 (1994)
  4. G. Di Marco, P.Favati, G. Lotti, and F. Romani, Asymptotic Behaviour of Automatic Quadrature, Journal of Complexity, 10, 296-340 (1994)
  5. G. Manzini, Sparse Matrix Vector Multiplication on Distribuited Architectures: Lower Bounds and Average Complexity Results, Information Processing Letters, 50, 231-238 (1994)
  6. G. Manzini, Sparse Matrix Computation on the Hypercube and Related Networks, Journal of Parallel and Distribuited Computing, 21, 169-183 (1994)

    1995

  7. M. Arioli, B. Codenotti, and C. Fassino, The Pade' Method for Computing the Matrix Exponential, Linear Algebra and Its Applications, (1995)
  8. I. Bar-On and B. Codenotti, A Fast and Stable Parallel QR Algorithm for Symmetric Tridiagonal Matrices, Linear Algebra and Its Applications, (1995)
  9. G.M. Del Corso, Randomization and the Parallel Solution of Linear Algebra Problems, Computers and Mathematics with Applications , 30(11), 59-72, (1995).
  10. P. Favati, G. Lotti, and F. Romani, Peano Kernel Behaviour and Error Bounds for Symmetric Quadrature Formulas, Computer and Mathematics with Applications, 29, 27-34 (1995)
  11. P. Favati, G. Lotti, and F. Romani, New Symmetric Interpolatory Quadrature, Calcolo, (1995)

    1996

  12. I. Bar-On, B. Codenotti, and M. Leoncini, Checking Robust Nonsingularity of Tridiagonal Matrices in Linear Time, BIT, (1996)
  13. A. Bernasconi, Sensitivity vs. Block Sensitivity (an average-case study), Information Processing Letters, 59, 151-157 (1996)
  14. V. Brimkov, B. Codenotti, M. Leoncini, and G. Resta, Strong NP-completeness of a Matrix Similarity Problem, Theoretical Computer Science, to appear, (1996)
  15. B. Codenotti and L. Margara, Transitive Cellular Automata are Sensitive, The American Mathematical Monthly, n.1 (1996)
  16. B. Codenotti, G. Manzini, and L. Margara, Algebraic Techniques in Communication Complexity, Information Processing Letters, (1996)
  17. B. Codenotti, G. Manzini, L. Margara, and G. Resta, Perturbation: An Efficient Technique for the Solution of Very Large Instances of the Euclidean TSP, ORSA J. Comput., (1996)
  18. P. Favati, G. Lotti, and L. Margara, Additive One-Dimensional Cellular Automata are Chaotic According to Devaney's Definition of Chaos, Theoretical Computer Science, (1996)
  19. M. Leoncini, On the parallel complexity of Gaussian Elimination with pivoting, Journal of Computer and System Science, to appear, (1996)
  20. M. Leoncini, Complexity vs. accuracy: some case studies, Journal of Complexity, to appear, (1996)
  21. M. Pellegrini, Repetitive Hidden Surface Removal for Polyhedra, Journal of Algorithms, 21:80-101 (1996)
  22. M. Pellegrini, On Point Location and Motion Planning among Simplices, SIAM Journal on Computing,25(5):1061-1081, October (1996)

    1997

  23. I. Bar-On, B. Codenotti, and M. Leoncini, A Fast Parallel Cholesky Decomposition Algorithm for Tridiagonal Symmetric Matrices, SIAM J. Matrix Analysis and Appl., Vol. 18(2) (1997) 403-418.
  24. B. Codenotti, B. N. Datta, K. Datta, M. Leoncini, Parallel Algorithms for Certain Matrix Computations, Theoretical Computer Science, 180 (1997) 287-308.
  25. B. Codenotti, V. Crespi, G. Resta, On the Permanent of Certain (0,1) Toeplitz Matrices, Linear Algebra and its Applications, 267 (1997) 65-100.
  26. G.M. Del Corso, Estimating an Eigenvector by the Power Method with a Random Start. SIAM Journal on Matrix Analysis and Applications , l 18(4), 913-937, (1997).
  27. G.M. Del Corso, G. Manzini, On the Randomized Error of Polynomial Methods for Eigenvector and Eigenvalue Estimate. Journal of Complexity, 13(4): 419-456, (1997).
  28. P. Favati, G. Fiorentino, G. Lotti, and F. Romani, Local error estimates and regularity tests for the implementation of Double Adaptive Quadrature, ACM Transaction on Mathematical Software, 23, 16-31 (1997)
  29. P. Favati, Asymptotic bit cost of quadrature formulas obtained by variable trasformation, Applied Mathematics Letters, 10, 1-7 (1997)
  30. L. Galli-Resta, G. Resta, S.-S. Tan and B. Reese, Mosaics of Islet-1 expressing amacrine cells assembled by short range cellular interactions, Journal of Neurosciences, (1997) 17: 7831-7838.
  31. M. Pellegrini, Monte Carlo Approximation of Form Factors with Error Bounded a Priori, Discrete & Computational Geometry, 17(3):319-338, April (1997).
  32. M. Pellegrini, On Counting Pairs of Intersecting Segments and Off-Line Triangle Range Searching, Algorithmica, 17(4):380-398, April (1997)

    1998

  33. A. Bernasconi, Harmonic Analysis and Boolean Function Complexity, Calcolo, Springer Verlag, 35, 149-186 (1998)
  34. B. Codenotti, I. Gerace, S. Vigna, On Some Combinatorial Questions Related to Circulant Graphs, Linear Algebra and its Applications, 285 (1998), 123-142.
  35. G. M. Del Corso, Metodi Probabilistici per il Calcolo di Autovalori ed Autovettori. Bollettino dell'Unione Matematica Italiana, Sezione A: La matematica nella societa' e nella cultura, 1-A Suppl: 185-188, (1998).
  36. P. Favati, B. Meini, Relaxed functional iteration techniques for the numerical solution of M/G/1 type Markov chains, BIT, 38, 510-526 (1998)
  37. D. Finocchiaro, M. Pellegrini and P. Bientinesi, On Numerical Approximation of Electrostatic Energy in 3D. Journal of Computational Physics, 146(2):707-725, (1998).
  38. M. Pellegrini, Electrostatic Fields without Singularities: Theory, Algorithms and Error Analysis. Journal of the ACM, 45(6):924-964, November (1998)

    1999

  39. R. Beigel, A. Bernasconi, A Note on the Polynomial Representation of Boolean Functions over GF(2), International Journal of Foundations of Computer Science, 10, 535-542 (1999)
  40. A. Bernasconi, On the Complexity of Balanced Boolean functions, Information Processing Letters, 70, 157-163 (1999)
  41. A. Bernasconi, L. Egidi, Hilbert function and complexity lower bounds for symmetric Boolean functions, Information and Computation, 153, 1-25 (1999)
  42. A. Bernasconi, B. Codenotti, Spectral Analysis of Boolean Functions as a Graph Eigenvalue Problem, IEEE Transactions on Computers, Vol. 48(3) (1999), 345-351.
  43. A. Bernasconi, B. Codenotti, V. Crespi, G. Resta, How fast can one compute the permanent of circulant matrices? Linear Algebra and its Applications, 292 (1-3) 1999, 15-37.
  44. G.M. Del Corso, G. Manzini, Finding Exact Solutions to the Bandwidth Minimization Problem. Computing, 62(3): 189-203, (1999).
  45. P. Favati, B. Meini, On functional iteration methods for solving nonlinear matrix equations arising in queueing problems, IMA Journal on Numerical Analysis, 19, 39-49 (1999)
  46. P. Favati, G. Lotti, O. Menchi and F. Romani, An infinite precision bracketing algorithm with guaranteed convergence, Numerical Algorithms,, 20, 63-73 (1999)

    2000 -

  47. A. Bernasconi, C. Damm, I. Shparlinski, Circuit and Decision Tree Complexity of Some Number Theoretic Problems, Information and Computation, to appear.
  48. A. Bernasconi, C. Damm, I. Shparlinski, The Average Sensitivity of Square-Freeness, Computational Complexity, to appear.
  49. D.A. Bini, G. M. Del Corso, G. Manzini, L. Margara, Inversion of Circulant Matrices over Zm. Mathematics of Computation, (to appear) 2000.
  50. B. Codenotti, Matrix Rigidity, Linear Algebra and its Applications, 304 (1-3) (2000), 181--192.
  51. B. Codenotti, G. Del Corso, G. Manzini, Matrix Rank and Communication Complexity, Linear Algebra and its Applications, 304 (1-3) (2000), 193--200.
  52. B. Codenotti, M. Leoncini, F.P. Preparata, The role of arithmetic in fast parallel matrix inversion, Algorithmica, accepted for publication.
  53. B. Codenotti, P. Pudlak, G. Resta Some structural properties of low rank matrices related to computational complexity, Theoretical Computer Science, Vol: 235 (1) (2000), pp. 89-107.
  54. G. M. Del Corso, Randomized Error Estimation for Eigenvalue Approximation. Calcolo , 37(1):21--46, (2000).
  55. P. Favati, M. Leoncini, and A. Martinez, On the robustness of Gaussian Elimination with Partial Pivoting, BIT, 40, 62-73 (2000).
  56. P. Favati, G. Lotti, O. Menchi and F. Romani, Separable Asymptotic Cost of Evaluating Elementary Functions, Numerical Algorithms, to appear, (2000).
  57. P. Favati, G. Lotti, O. Menchi and F. Romani, Solution of Infinite Linear Systems by Automatic Adaptive Iterations, Linear Algebra and its Applications, to appear, (2000).
  58. P. Favati, G. Lotti, and O. Menchi, Matrix Form of a Multi-queue Problem, Acta Technica, to appear, (2000).
  59. P. Favati, G. Lotti, O. Menchi and F. Romani, Efficient Solution of Sparse Block Hessenberg Systems, Acta Technica, to appear, (2000).
  60. P. Favati, B. Meini, Solving certain queueing problems by means of regular splittings, Applied Mathematics Letters, 13, 99-105 (2000).

Conference papers

  1. A. Bernasconi and B. Codenotti, Measures of Boolean Function Complexity Based on Harmonic Analysis, CIAC 94, Lecture Notes in Computer Science 778, Rome, Italy (1994)
  2. B. Codenotti, Obstacles in the Development of Very Fast Parallel Algorithms, DAGS School, Dartmouth College, Hanover, USA (1994)
  3. B. Codenotti, Some Ideas for a Theory of Numerical Analysis, AMS Workshop on Continuous Algorithms and Complexity, Mt. Holyoke College, MA USA (1994)
  4. M. Blum, B. Codenotti, P. Gemmell, and T. Shahoumian, Self-Correcting for Function of Finite Trascendental Degree, Proceedings of the 22nd International Colloquium ICALP95, Szeged, Hungary, LNCS 944, p547-557 (1995)
  5. B. Codenotti, P. Gemmell, and J. Simon, Average Communication Complexity and Average Circuit Depth, ESA95, Corfu', Greece, (1995)
  6. B. Codenotti and L. Margara, Chaos in Mathematics, Physics, and Computer Science: Similarities and Dissimilarities, The Evolution of Complexity, Bruxelles (1995)
  7. P. Boldi, B. Codenotti, P. Gemmell, S. Shammah, J. Simon, and S. Vigna, Symmetry Breaking in Anonymous Networks: Characterizations, Proc. 4th Israel Symposium on Theory of Computing and Systems, pp. 16-26 (1996)
  8. M. Leoncini, G. Manzini, and L. Margara, Parallel complexity of Householder QR factorization, ESA96, (1996)
  9. M. Pellegrini, Electrostatic Fields without Singularities: Theory and Algorithms, Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms, pages 184-191, January 1996 January 1996
  10. A. Bernasconi, On the Complexity of Balanced Boolean functions, 3rd Italian Conference on Algorithms and Complexity CIAC 97, , Lecture Notes in Computer Science 1203, Rome, Italy (1997)
  11. A. Bernasconi, B.Codenotti, V. Crespi, G. Resta, Groebner Bases in the Boolean Setting with Application to Counting, Proc. Workshop on Algorithms Engineering 97.
  12. G. Bilardi, B. Codenotti, G. Del Corso, C. Pinotti, G. Resta, Broadcast and Other primitive Operations on Fat Trees, Proc. EURO-PAR 97, Lecture Notes In Computer Science 1300, pp. 196-207.
  13. B. Codenotti, F.Ergun, P. Gemmell, R.Kumar, Checking Properties of Polynomials, Proceedings of the 24th International Colloquium ICALP 97, Lecture Notes In Computer Science 1256.
  14. B. Codenotti, P. Gemmell, P. Pudlak, J. Simon, On the amount of randomness needed in distributed computations, Proc. OPODIS 97, pp. 237-248 (1997).
  15. P. Favati, G. Fiorentino, G. Lotti, and F. Romani, A Mathematica implementation of Double Adaptive Quadrature, Innovation in Mathematics, proceedings of the second international Mathematica Symposium, pp. 145-151 Finlandia(1997)
  16. Codenotti, B. Mariotti, G. Pedinotti, S. and Resta, G., Parallel Implementation of a Discontinuous Finite Element Method for the Solution of the Navier-Stokes Equations, Parallel CFD97, Manchester, UK, May 1997 (Proceedings in "Recent Developments and Advances Using Parallel Computers", Emerson et al. Eds, Elsevier Science 1998, pp. 257-262).
  17. A. Bernasconi, Combinatorial Properties of Classes of Functions Hard to Compute in Constant Depth, 4th Int. Computing and Combinatorics Conference COCOON 98, Lecture Notes in Computer Science 1449, Taipei, ROC (1998)
  18. A. Bernasconi, On Boolean Functions Satisfying Odd Order Propagation Criteria, 3rd International Workshop on Boolean Problems IWBP 98, Freiberg, Germany (1998)
  19. A. Bernasconi, On the Polynomial Representation of Boolean Functions over GF(2), 6th Italian Conference on Theoretical Computer Science ICTCS 98, Prato, Italy, World Scientific Press (1998)
  20. D. A. Bini, G. M. Del Corso, G. Manzini, L. Margara, Inversion of Circulant Matrices overZm. International Colloquium on Automata Languages and Programming, Aalborg, Danimarca, LNCS 1998.
  21. P. Favati, B. Meini, On functional iteration methods for solving M/G/1 type Markov chains, in Advances in Matrix Analytic Methods for Stochastic Models, Proceedings of the 2nd International Conference on Matrix Analytic Methods, A. Alfa and S.Chakravarthy (Editors), 1998.
  22. L. Bedini, G. M. Del Corso, A. Tonazzini, A Preconditioning Technique for Edge-Preserving Image Restoration. IEEE International Conference on Information, Intelligence, Systems , Washington, USA, 1999.
  23. A. Bernasconi, I. Shparlinski, Circuit Complexity of Testing Square-Free Numbers, 16th International Symposium on Theoretical Aspects in Computer Science STACS 99, Lectures Notes in Computer Science 1563, Trier, Germany (1999)
  24. A. Bernasconi, C. Damm, I. Shparlinski, On the Average Sensitivity of Testing Square-free numbers, 5th Int. Computing and Combinatorics Conference COCOON 99, Lectures Notes in Computer Science 1627, Tokyo, Japan (1999)
  25. D. Finocchiaro and M. Pellegrini, On computing the diameter of a point set in high dimensional Euclidean space. In Proceedings of the Seventh Annual European Symposium on Algorithms. Lecture Notes in Computer Science 1643, pages 366-377, 1999.
  26. M. Pellegrini, A Geometric Approach to Computing Higher Order Form Factors In Proceedings of the 15th ACM Symposium on Computational Geometry, pages 69-78, 1999.
  27. M. Pellegrini, Rendering equation revisited: how to avoid explicit visibility computations. In Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms, pages 725-733, 1999.
  28. A. Bernasconi, B.Codenotti, On Boolean Functions associated to Bipartite Cayley Graphs, 4th International Workshop on Boolean Problems, (September, 2000).
  29. V. Brimkov, B. Codenotti, V. Crespi, M. Leoncini, On the Lovasz number of certain circulant graphs, Proc. CIAC 2000 (Rome, 2000), Lecture Notes In Computer Science 1767, pp. 291-305.

Books and Chapters in Books

  1. M. Pellegrini, Ray-shooting and lines in space, The CRC Handbook of Discrete and Computational Geometry, Jacob E. Goodman and Joseph O'Rourke (eds.). CRC Press, Boca Raton, Florida, pp. 599-614, (1997)
  2. A. Bernasconi, B. Codenotti, Introduzione alla Complessita' Computazionale, (in Italian) Springer Verlag (1998).
  3. A. Bernasconi, B. Codenotti and G. Resta Metodi Matematici in Complessita' Computazionale, (in Italian) Springer Verlag (1999).
  4. B. Codenotti, M. Leoncini and G. Resta, A Java Framework for Internet Distributed Computations, in: E. N. Houstis, J. R. Rice, E. Gallopoulos e R. Bramley, Enabling Technologies for Computational Science: Frameworks, Middleware and Environments, Kluwer Academic Publishers, (2000)
  5. B. Codenotti, G. Resta, On the Permanent of Certain Circulant Matrices, in: D. Senato Ed., Algebraic Combinatorics and Theoretical Computer Science, a tribute to Gian Carlo Rota, Springer-Verlag, to appear.


Back to IMC home page