Coverage for /usr/lib/python3/dist-packages/sympy/matrices/sparse.py: 27%

1from collections.abc import Callable

3from sympy.core.containers import Dict

4from sympy.utilities.exceptions import sympy_deprecation_warning

5from sympy.utilities.iterables import is_sequence

6from sympy.utilities.misc import as_int

8from .matrices import MatrixBase

9from .repmatrix import MutableRepMatrix, RepMatrix

11from .utilities import _iszero

13from .decompositions import (

14 _liupc, _row_structure_symbolic_cholesky, _cholesky_sparse,

15 _LDLdecomposition_sparse)

17from .solvers import (

18 _lower_triangular_solve_sparse, _upper_triangular_solve_sparse)

21class SparseRepMatrix(RepMatrix):

22 """

23 A sparse matrix (a matrix with a large number of zero elements).

25 Examples

26 ========

28 >>> from sympy import SparseMatrix, ones

29 >>> SparseMatrix(2, 2, range(4))

30 Matrix([

31 [0, 1],

32 [2, 3]])

33 >>> SparseMatrix(2, 2, {(1, 1): 2})

34 Matrix([

35 [0, 0],

36 [0, 2]])

38 A SparseMatrix can be instantiated from a ragged list of lists:

40 >>> SparseMatrix([[1, 2, 3], [1, 2], [1]])

41 Matrix([

42 [1, 2, 3],

43 [1, 2, 0],

44 [1, 0, 0]])

46 For safety, one may include the expected size and then an error

47 will be raised if the indices of any element are out of range or

48 (for a flat list) if the total number of elements does not match

49 the expected shape:

51 >>> SparseMatrix(2, 2, [1, 2])

52 Traceback (most recent call last):

53 ...

54 ValueError: List length (2) != rows*columns (4)

56 Here, an error is not raised because the list is not flat and no

57 element is out of range:

59 >>> SparseMatrix(2, 2, [[1, 2]])

60 Matrix([

61 [1, 2],

62 [0, 0]])

64 But adding another element to the first (and only) row will cause

65 an error to be raised:

67 >>> SparseMatrix(2, 2, [[1, 2, 3]])

68 Traceback (most recent call last):

69 ...

70 ValueError: The location (0, 2) is out of designated range: (1, 1)

72 To autosize the matrix, pass None for rows:

74 >>> SparseMatrix(None, [[1, 2, 3]])

75 Matrix([[1, 2, 3]])

76 >>> SparseMatrix(None, {(1, 1): 1, (3, 3): 3})

77 Matrix([

78 [0, 0, 0, 0],

79 [0, 1, 0, 0],

80 [0, 0, 0, 0],

81 [0, 0, 0, 3]])

83 Values that are themselves a Matrix are automatically expanded:

85 >>> SparseMatrix(4, 4, {(1, 1): ones(2)})

86 Matrix([

87 [0, 0, 0, 0],

88 [0, 1, 1, 0],

89 [0, 1, 1, 0],

90 [0, 0, 0, 0]])

92 A ValueError is raised if the expanding matrix tries to overwrite

93 a different element already present:

95 >>> SparseMatrix(3, 3, {(0, 0): ones(2), (1, 1): 2})

96 Traceback (most recent call last):

97 ...

98 ValueError: collision at (1, 1)

100 See Also

101 ========

102 DenseMatrix

103 MutableSparseMatrix

104 ImmutableSparseMatrix

105 """

106

107 @classmethod

108 def _handle_creation_inputs(cls, *args, **kwargs):

109 if len(args) == 1 and isinstance(args[0], MatrixBase):

110 rows = args[0].rows

111 cols = args[0].cols

112 smat = args[0].todok()

113 return rows, cols, smat

114

115 smat = {}

116 # autosizing

117 if len(args) == 2 and args[0] is None:

118 args = [None, None, args[1]]

119

120 if len(args) == 3:

121 r, c = args[:2]

122 if r is c is None:

123 rows = cols = None

124 elif None in (r, c):

125 raise ValueError(

126 'Pass rows=None and no cols for autosizing.')

127 else:

128 rows, cols = as_int(args[0]), as_int(args[1])

129

130 if isinstance(args[2], Callable):

131 op = args[2]

132

133 if None in (rows, cols):

134 raise ValueError(

135 "{} and {} must be integers for this "

136 "specification.".format(rows, cols))

137

138 row_indices = [cls._sympify(i) for i in range(rows)]

139 col_indices = [cls._sympify(j) for j in range(cols)]

140

141 for i in row_indices:

142 for j in col_indices:

143 value = cls._sympify(op(i, j))

144 if value != cls.zero:

145 smat[i, j] = value

146

147 return rows, cols, smat

148

149 elif isinstance(args[2], (dict, Dict)):

150 def update(i, j, v):

151 # update smat and make sure there are no collisions

152 if v:

153 if (i, j) in smat and v != smat[i, j]:

154 raise ValueError(

155 "There is a collision at {} for {} and {}."

156 .format((i, j), v, smat[i, j])

157 )

158 smat[i, j] = v

159

160 # manual copy, copy.deepcopy() doesn't work

161 for (r, c), v in args[2].items():

162 if isinstance(v, MatrixBase):

163 for (i, j), vv in v.todok().items():

164 update(r + i, c + j, vv)

165 elif isinstance(v, (list, tuple)):

166 _, _, smat = cls._handle_creation_inputs(v, **kwargs)

167 for i, j in smat:

168 update(r + i, c + j, smat[i, j])

169 else:

170 v = cls._sympify(v)

171 update(r, c, cls._sympify(v))

172

173 elif is_sequence(args[2]):

174 flat = not any(is_sequence(i) for i in args[2])

175 if not flat:

176 _, _, smat = \

177 cls._handle_creation_inputs(args[2], **kwargs)

178 else:

179 flat_list = args[2]

180 if len(flat_list) != rows * cols:

181 raise ValueError(

182 "The length of the flat list ({}) does not "

183 "match the specified size ({} * {})."

184 .format(len(flat_list), rows, cols)

185 )

186

187 for i in range(rows):

188 for j in range(cols):

189 value = flat_list[i*cols + j]

190 value = cls._sympify(value)

191 if value != cls.zero:

192 smat[i, j] = value

193

194 if rows is None: # autosizing

195 keys = smat.keys()

196 rows = max([r for r, _ in keys]) + 1 if keys else 0

197 cols = max([c for _, c in keys]) + 1 if keys else 0

198

199 else:

200 for i, j in smat.keys():

201 if i and i >= rows or j and j >= cols:

202 raise ValueError(

203 "The location {} is out of the designated range"

204 "[{}, {}]x[{}, {}]"

205 .format((i, j), 0, rows - 1, 0, cols - 1)

206 )

207

208 return rows, cols, smat

209

210 elif len(args) == 1 and isinstance(args[0], (list, tuple)):

211 # list of values or lists

212 v = args[0]

213 c = 0

214 for i, row in enumerate(v):

215 if not isinstance(row, (list, tuple)):

216 row = [row]

217 for j, vv in enumerate(row):

218 if vv != cls.zero:

219 smat[i, j] = cls._sympify(vv)

220 c = max(c, len(row))

221 rows = len(v) if c else 0

222 cols = c

223 return rows, cols, smat

224

225 else:

226 # handle full matrix forms with _handle_creation_inputs

227 rows, cols, mat = super()._handle_creation_inputs(*args)

228 for i in range(rows):

229 for j in range(cols):

230 value = mat[cols*i + j]

231 if value != cls.zero:

232 smat[i, j] = value

233

234 return rows, cols, smat

235

236 @property

237 def _smat(self):

238

239 sympy_deprecation_warning(

240 """

241 The private _smat attribute of SparseMatrix is deprecated. Use the

242 .todok() method instead.

243 """,

244 deprecated_since_version="1.9",

245 active_deprecations_target="deprecated-private-matrix-attributes"

246 )

247

248 return self.todok()

249

250 def _eval_inverse(self, **kwargs):

251 return self.inv(method=kwargs.get('method', 'LDL'),

252 iszerofunc=kwargs.get('iszerofunc', _iszero),

253 try_block_diag=kwargs.get('try_block_diag', False))

254

255 def applyfunc(self, f):

256 """Apply a function to each element of the matrix.

257

258 Examples

259 ========

260

261 >>> from sympy import SparseMatrix

262 >>> m = SparseMatrix(2, 2, lambda i, j: i*2+j)

263 >>> m

264 Matrix([

265 [0, 1],

266 [2, 3]])

267 >>> m.applyfunc(lambda i: 2*i)

268 Matrix([

269 [0, 2],

270 [4, 6]])

271

272 """

273 if not callable(f):

274 raise TypeError("`f` must be callable.")

275

276 # XXX: This only applies the function to the nonzero elements of the

277 # matrix so is inconsistent with DenseMatrix.applyfunc e.g.

278 # zeros(2, 2).applyfunc(lambda x: x + 1)

279 dok = {}

280 for k, v in self.todok().items():

281 fv = f(v)

282 if fv != 0:

283 dok[k] = fv

284

285 return self._new(self.rows, self.cols, dok)

286

287 def as_immutable(self):

288 """Returns an Immutable version of this Matrix."""

289 from .immutable import ImmutableSparseMatrix

290 return ImmutableSparseMatrix(self)

291

292 def as_mutable(self):

293 """Returns a mutable version of this matrix.

294

295 Examples

296 ========

297

298 >>> from sympy import ImmutableMatrix

299 >>> X = ImmutableMatrix([[1, 2], [3, 4]])

300 >>> Y = X.as_mutable()

301 >>> Y[1, 1] = 5 # Can set values in Y

302 >>> Y

303 Matrix([

304 [1, 2],

305 [3, 5]])

306 """

307 return MutableSparseMatrix(self)

308

309 def col_list(self):

310 """Returns a column-sorted list of non-zero elements of the matrix.

311

312 Examples

313 ========

314

315 >>> from sympy import SparseMatrix

316 >>> a=SparseMatrix(((1, 2), (3, 4)))

317 >>> a

318 Matrix([

319 [1, 2],

320 [3, 4]])

321 >>> a.CL

322 [(0, 0, 1), (1, 0, 3), (0, 1, 2), (1, 1, 4)]

323

324 See Also

325 ========

326

327 sympy.matrices.sparse.SparseMatrix.row_list

328 """

329 return [tuple(k + (self[k],)) for k in sorted(self.todok().keys(), key=lambda k: list(reversed(k)))]

330

331 def nnz(self):

332 """Returns the number of non-zero elements in Matrix."""

333 return len(self.todok())

334

335 def row_list(self):

336 """Returns a row-sorted list of non-zero elements of the matrix.

337

338 Examples

339 ========

340

341 >>> from sympy import SparseMatrix

342 >>> a = SparseMatrix(((1, 2), (3, 4)))

343 >>> a

344 Matrix([

345 [1, 2],

346 [3, 4]])

347 >>> a.RL

348 [(0, 0, 1), (0, 1, 2), (1, 0, 3), (1, 1, 4)]

349

350 See Also

351 ========

352

353 sympy.matrices.sparse.SparseMatrix.col_list

354 """

355 return [tuple(k + (self[k],)) for k in

356 sorted(self.todok().keys(), key=list)]

357

358 def scalar_multiply(self, scalar):

359 "Scalar element-wise multiplication"

360 return scalar * self

361

362 def solve_least_squares(self, rhs, method='LDL'):

363 """Return the least-square fit to the data.

364

365 By default the cholesky_solve routine is used (method='CH'); other

366 methods of matrix inversion can be used. To find out which are

367 available, see the docstring of the .inv() method.

368

369 Examples

370 ========

371

372 >>> from sympy import SparseMatrix, Matrix, ones

373 >>> A = Matrix([1, 2, 3])

374 >>> B = Matrix([2, 3, 4])

375 >>> S = SparseMatrix(A.row_join(B))

376 >>> S

377 Matrix([

378 [1, 2],

379 [2, 3],

380 [3, 4]])

381

382 If each line of S represent coefficients of Ax + By

383 and x and y are [2, 3] then S*xy is:

384

385 >>> r = S*Matrix([2, 3]); r

386 Matrix([

387 [ 8],

388 [13],

389 [18]])

390

391 But let's add 1 to the middle value and then solve for the

392 least-squares value of xy:

393

394 >>> xy = S.solve_least_squares(Matrix([8, 14, 18])); xy

395 Matrix([

396 [ 5/3],

397 [10/3]])

398

399 The error is given by S*xy - r:

400

401 >>> S*xy - r

402 Matrix([

403 [1/3],

404 [1/3],

405 [1/3]])

406 >>> _.norm().n(2)

407 0.58

408

409 If a different xy is used, the norm will be higher:

410

411 >>> xy += ones(2, 1)/10

412 >>> (S*xy - r).norm().n(2)

413 1.5

414

415 """

416 t = self.T

417 return (t*self).inv(method=method)*t*rhs

418

419 def solve(self, rhs, method='LDL'):

420 """Return solution to self*soln = rhs using given inversion method.

421

422 For a list of possible inversion methods, see the .inv() docstring.

423 """

424 if not self.is_square:

425 if self.rows < self.cols:

426 raise ValueError('Under-determined system.')

427 elif self.rows > self.cols:

428 raise ValueError('For over-determined system, M, having '

429 'more rows than columns, try M.solve_least_squares(rhs).')

430 else:

431 return self.inv(method=method).multiply(rhs)

432

433 RL = property(row_list, None, None, "Alternate faster representation")

434 CL = property(col_list, None, None, "Alternate faster representation")

435

436 def liupc(self):

437 return _liupc(self)

438

439 def row_structure_symbolic_cholesky(self):

440 return _row_structure_symbolic_cholesky(self)

441

442 def cholesky(self, hermitian=True):

443 return _cholesky_sparse(self, hermitian=hermitian)

444

445 def LDLdecomposition(self, hermitian=True):

446 return _LDLdecomposition_sparse(self, hermitian=hermitian)

447

448 def lower_triangular_solve(self, rhs):

449 return _lower_triangular_solve_sparse(self, rhs)

450

451 def upper_triangular_solve(self, rhs):

452 return _upper_triangular_solve_sparse(self, rhs)

453

454 liupc.__doc__ = _liupc.__doc__

455 row_structure_symbolic_cholesky.__doc__ = _row_structure_symbolic_cholesky.__doc__

456 cholesky.__doc__ = _cholesky_sparse.__doc__

457 LDLdecomposition.__doc__ = _LDLdecomposition_sparse.__doc__

458 lower_triangular_solve.__doc__ = lower_triangular_solve.__doc__

459 upper_triangular_solve.__doc__ = upper_triangular_solve.__doc__

460

461

462class MutableSparseMatrix(SparseRepMatrix, MutableRepMatrix):

463

464 @classmethod

465 def _new(cls, *args, **kwargs):

466 rows, cols, smat = cls._handle_creation_inputs(*args, **kwargs)

467

468 rep = cls._smat_to_DomainMatrix(rows, cols, smat)

469

470 return cls._fromrep(rep)

471

472

473SparseMatrix = MutableSparseMatrix