zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
The ubiquitous Kronecker product. (English) Zbl 0966.65039
The author gives a tutorial in applications of Kronecker product computations including linear matrix equation problems, fast linear transforms, various optimization problems, and preconditioning with Kronecker products.

MSC:
65F30Other matrix algorithms
15A69Multilinear algebra, tensor products
15A24Matrix equations and identities
65T50Discrete and fast Fourier transforms (numerical methods)
65K05Mathematical programming (numerical methods)
Software:
Algorithm 705
WorldCat.org
Full Text: DOI
References:
[1] Andre, T. F.; Nowak, R. D.; Van Veen, B. D.: Low rank estimation of higher order statistics. IEEE trans. Signal process. 45, 673-685 (1997)
[2] Andrews, H. C.; Kane, J.: Kronecker matrices, computer implementation, and generalized spectra. J. assoc. Comput. Mach 17, 260-268 (1970) · Zbl 0196.17203
[3] Barham, R. H.; Drane, W.: An algorithm for least squares estimation of nonlinear parameters when some of the parameters are linear. Technometrics 14, 757-766 (1972) · Zbl 0237.62025
[4] Barrlund, A.: Efficient solution of constrained least squares problems with Kronecker product structure. SIAM J. Matrix anal. Appl. 19, 154-160 (1998) · Zbl 0913.65033
[5] Bartels, R. H.; Stewart, G. W.: Solution of the equation AX +XB = C. Comm. ACM 15, 820-826 (1972)
[6] Brewer, J. W.: Kronecker products and matrix calculus in system theory. IEEE trans. Circuits systems 25, 772-781 (1978) · Zbl 0397.93009
[7] Calvetti, D.; Reichel, L.: Application of ADI iterative methods to the image restoration of noisy images. SIAM J. Matrix anal. Appl. 17, 165-174 (1996) · Zbl 0849.65101
[8] Chan, T. F.: An optimal circulant preconditioner for Toeplitz systems. SIAM J. Sci. statist. Comput. 9, 766-771 (1988) · Zbl 0646.65042
[9] Chan, T. F.; Olkin, J. A.: Preconditioners for Toeplitz-block matrices. Numer. algorithms 6, 89-101 (1993) · Zbl 0793.65020
[10] Chan, R.; Jin, X. -Q.: A family of block preconditioners for block systems. SIAM J. Sci. statist. Comput. 13, 1218-1235 (1992) · Zbl 0760.65027
[11] T.F. Coleman, Y. Li, A. Mariano, Separation of pulmonary nodule images using total variation minimization, Technical Report, Cornell Theory Center, Ithaca, New York, 1998.
[12] Cullum, J.; Willoughby, R. A.: Lanczos algorithms for large sparse symmetric eigenvalue computations, vol. I (Theory), II (Programs). (1985) · Zbl 0574.65028
[13] Datta, K.: The matrix equation XA - BX = R and its applications. Linear algebra appl. 109, 91-105 (1988) · Zbl 0656.15006
[14] Davio, M.: Kronecker products and shuffle algebra. IEEE trans. Comput. 30, 116-125 (1981) · Zbl 0455.94050
[15] Davis, P.; Rabinowitz, P.: Numerical integration. (1967) · Zbl 0154.17802
[16] De Boor, C.: A practical guide to splines. (1978) · Zbl 0406.41003
[17] De Boor, C.: Efficient computer manipulation of tensor products. ACM trans. Math. software 5, 173-182 (1979) · Zbl 0405.65011
[18] Dorr, F. W.: The direct solution of the discrete Poisson equation on a rectangle. SIAM rev. 12, 248-263 (1970) · Zbl 0208.42403
[19] Dutt, A.; Rokhlin, V.: Fast Fourier transforms for nonequispaced data. SIAM J. Sci. comput. 14, 1368-1398 (1993) · Zbl 0791.65108
[20] L. Eldin, I. Skoglund, Algorithms for the regularization of Ill-conditioned least squares problems with tensor product structure and applications to space-variant image restoration, Technical Report LiTH-Mat-R-82-48, Department of Mathematics, Linkoping University, Sweden, 1982.
[21] Fausett, D. W.; Fulton, C. T.: Large least squares problems involving Kronecker products. SIAM J. Matrix anal. 15, 219-227 (1994) · Zbl 0798.65059
[22] Fausett, D. W.; Fulton, C. T.; Hashish, H.: Improved parallel QR method for large least squares problems involving Kronecker products. J. comput. Appl. math. (1997) · Zbl 0868.65019
[23] A. Fijany, C.P. Williams, Quantum wavelet transforms: fast algorithms and complete circuits, Technical Report 9809004, Los Alamos National Laboratory, Los Alamos, New Mexico, 1998. · Zbl 0939.42020
[24] Gardiner, J.; Wette, M. R.; Laub, A. J.; Amato, J. J.; Moler, C. B.: Algorithm 705: a Fortran-77 software package for solving the Sylvester matrix equation AXBT + CXDT = E. ACM trans. Math. software 18, 232-238 (1992) · Zbl 0893.65027
[25] Golub, G. H.: Some modified eigenvalue problems. SIAM rev. 15, 318-344 (1973) · Zbl 0254.65027
[26] Golub, G. H.; Luk, F.; Overton, M.: A block lanzcos method for computing the singular values and corresponding singular vectors of a matrix. ACM trans. Math. software 7, 149-169 (1981) · Zbl 0466.65022
[27] Golub, G. H.; Nash, S.; Van Loan, C.: A Hessenberg-Schur method for the matrix problem AX + XB = C. IEEE trans. Automat. control 24, 909-913 (1979) · Zbl 0421.65022
[28] Golub, G. H.; Pereya, V.: The differentiation of pseudoinverses and nonlinear least squares problems whose variables separate. SIAM J. Numer. anal. 10, 413-432 (1973) · Zbl 0258.65045
[29] Golub, G. H.; Van Loan, C.: Matrix computations. (1996) · Zbl 0865.65009
[30] Graham, A.: Kronecker products and matrix calculus with applications. (1981) · Zbl 0497.26005
[31] Granata, J.; Conner, M.; Tolimieri, R.: Recursive fast algorithms and the role of the tensor product. IEEE trans. Signal process. 40, 2921-2930 (1992) · Zbl 0771.65098
[32] Granata, J.; Conner, M.; Tolimieri, R.: The tensor product: a mathematical programming language for ffts and other fast DSP operations. IEEE SP mag., 40-48 (January 1992)
[33] Greengard, L.; Strain, J.: The fast Gauss transform. SIAM J. Sci. statist. Comput. 12, 79-94 (1991) · Zbl 0721.65089
[34] S.R Heap, D.J. Lindler, Block iterative restoration of astronomical images with the massively parallel processor Proceedings of the First Aerospace Symposium on Massively Parallel Scientific Computation, 1986, pp. 99--109.
[35] Henderson, H. V.; Pukelsheim, F.; Searle, S. R.: On the history of the Kronecker product. Linear multilinear algebra 14, 113-120 (1983) · Zbl 0517.15017
[36] Henderson, H. V.; Searle, S. R.: The vec-permutation matrix, the vec operator and Kronecker products: a review. Linear multilinear algebra 9, 271-288 (1981) · Zbl 0458.15006
[37] Horn, R. A.; Johnson, C. A.: Topics in matrix analysis. (1991) · Zbl 0729.15001
[38] R.M. Hristev, private communication, 1998.
[39] Huang, C-H.; Johnson, J. R.; Johnson, R. W.: Multilinear algebra and parallel programming. J. supercomput. 5, 189-217 (1991) · Zbl 0748.65042
[40] Jain, A. K.: Fundamentals of digital image processing. (1989) · Zbl 0744.68134
[41] Johnson, J.; Johnson, R. W.; Rodriguez, D.; Tolimieri, R.: A methodology for designing, modifying, and implementing Fourier transform algorithms on various architectures. Circuits systems signal process. 9, 449-500 (1990) · Zbl 0716.65131
[42] Kagstrom, B.: Perturbation analysis of the generalized Sylvester equation (AR-LB,DR-LE) = (C,F). SIAM J. Matrix anal. Appl. 15, 1045-1060 (1994)
[43] J. Kamm, J.G. Nagy, Kronecker product and SVD approximations in image restoration, Linear Algebra Appli. (1998a), to appear. · Zbl 0936.65052
[44] J. Kamm, J.G. Nagy, Kronecker product and SVD approximations for separable spatially variant blurs, SMU Mathematics Technical Report 98-04, Dallas, TX, 1998b. · Zbl 0936.65052
[45] J. Kamm, J.G. Nagy, Optimal kronecker product approximation of block Toeplitz matrices, SMU Mathematics Technical Report 98-05, Dallas, TX, 1998c. · Zbl 0969.65033
[46] Kaufman, L.: A variable projection method for solving separable nonlinear least squares problems. Bit 15, 49-57 (1975) · Zbl 0307.65019
[47] Klaus, B.; Horn, P.: Robot vision. (1990)
[48] B. Kumar, C.H. Huang, J. Johnson, R.W. Johnson, P. Sadayappan, A tensor product formulation of Strassen’s matrix multiplication algorithm with memory reduction, Seventh International Parallel Processing Symposium, 1993, pp. 582--588.
[49] Lancaster, P.: Explicit solution of linear matrix equations. SIAM rev. 12, 544-566 (1970) · Zbl 0209.06502
[50] Moler, C. B.; Stewart, G. W.: An algorithm for generalized matrix eigenvalue problems. SIAM J. Numer. anal. 10, 241-256 (1973) · Zbl 0253.65019
[51] J.G. Nagy, Decomposition of block Toeplitz matrices into a sum of Kronecker products with applications in image processing, SMU Mathematics Technical Report 96-01, Dallas, TX, 1996.
[52] Nagy, J. G.; O’leary, D. P.: Restoring images degraded by spatially-variant blur. SIAM J. Sci. comput. 19, 1063-1082 (1998) · Zbl 0919.65091
[53] Nowak, R. D.: Penalized least squares estimation of higher order statistics. IEEE trans. Signal process. 46, 419-428 (1998)
[54] Nowak, R. D.; Van Veen, B.: Tensor product basis approximations for Volterra filters. IEEE trans signal process. 44, 36-50 (1996)
[55] Pereyra, V.; Scherer, G.: Efficient computer manipulation of tensor products with applications to multidimensional approximation. Math. comp. 27, 595-604 (1973) · Zbl 0282.65019
[56] N.P. Pitsianis, The Kronecker product in approximation, fast transform generation, Ph.D. Thesis, Department of Computer Science, Cornell University, 1997.
[57] Pollard, J. H.: On the use of the direct matrix product in analyzing certain stochastic population models. Biometrika 53, 397-415 (1966) · Zbl 0144.43901
[58] Rauhala, U. A.: Introduction to array algebra. Photogrammetric eng. Remote sensing 46, No. 2, 177-182 (1980)
[59] Rauhala, U. A.; Davis, D.; Baker, K.: Automated DTM validation and progressive sampling algorithm of finite element array relaxation. Photogrammetric eng. Remote sensing 55, 449-465 (1989)
[60] Regalia, P. A.; Mitra, S.: Kronecker products, unitary matrices, and signal processing applications. SIAM rev. 31, 586-613 (1989) · Zbl 0687.15010
[61] Seberry, J.; Zhang, X-M.: Some orthogonal matrices constructed by strong Kronecker product multiplication. Austral. J. Combin. 7, 213-224 (1993) · Zbl 0779.05013
[62] Snay, R. A.: Applicability of array algebra. Rev. geophys. Space phys. 16, 459-464 (1978)
[63] Steeb, W-H.: Matrix calculus and Kronecker product with applications and C++ programs. (1997) · Zbl 0952.15019
[64] Stenger, F.: Kronecker product extensions of linear operators. SIAM J. Numer. anal. 5, 422-435 (1968) · Zbl 0165.17801
[65] L. Stiller, Multilinear algebra and chess endgames, in: Computational Games, Vol. 29, MSRI Publications. · Zbl 0872.90147
[66] Strohmer, T.: Numerical algorithms for discrete Gabor expansions. Gabor analysis and algorithms, 267-294 (1998) · Zbl 0890.42013
[67] Swami, A.; Mendel, J.: Time and lag recursive computation of cumulants from a state-space model. IEEE trans. Automat. control 35, 4-17 (1990) · Zbl 0712.93070
[68] S. Thirumalai, High performance algorithms to solve Toeplitz and block Toeplitz matrices, Ph.D. Thesis, University of Illinois, Urbana, IL, 1996. · Zbl 0859.65017
[69] M.J. Todd, On search directions in interior point methods for semidefinite programming, Optim. Methods Software, (1998), to appear.
[70] Tolimieri, R.; An, M.; Lu, C.: Algorithms for discrete Fourier transform and convolution. (1989) · Zbl 0705.65105
[71] Vandenberghe, L.; Boyd, S.: Semidefinite programming. SIAM rev. 38, 27-48 (1996) · Zbl 0845.65023
[72] Van Loan, C.: Computational frameworks for the fast Fourier transform. (1992) · Zbl 0757.65154
[73] Van Loan, C.; Pitsianis, N. P.: Approximation with Kronecker products. Linear algebra for large scale and real time applications, 293-314 (1992) · Zbl 0813.65078
[74] Vetter, W. J.: Vector structures, solutions of linear matrix equations. Linear algebra appl. 10, 181-188 (1975) · Zbl 0307.15003