





"""simple docstring"""




from typing import Any

import numpy as np





def 		UpperCAmelCase__						(	_UpperCAmelCase   ):






  """simple docstring"""





  assert np.shape(_UpperCAmelCase   )[0] == np.shape(_UpperCAmelCase   )[1]

  # If matrix not symmetric, exit right away.
  if np.allclose(_UpperCAmelCase					,   matrix.T   ) is False:
    return False

  # Get eigenvalues and eignevectors for a symmetric matrix.
  A_		,			A_    :			Any									=    np.linalg.eigh(_UpperCAmelCase   )

  # Check sign of all eigenvalues.
  # np.all returns a value of type np.bool_
  return bool(np.all(eigen_values > 0   )   )





def 		UpperCAmelCase__						(	_UpperCAmelCase   ):






  """simple docstring"""





  A_    :			str									=    np.random.randn(_UpperCAmelCase					,   _UpperCAmelCase   )
  A_    :			str									=    np.dot(_UpperCAmelCase					,   random_matrix.T   )
  assert _is_matrix_spd(_UpperCAmelCase   )
  return spd_matrix





def 		UpperCAmelCase__						(	_UpperCAmelCase					,   _UpperCAmelCase					,   _UpperCAmelCase = 1000					,   _UpperCAmelCase = 1E-8					,   ):






  """simple docstring"""





  assert np.shape(_UpperCAmelCase   )[0] == np.shape(_UpperCAmelCase   )[1]
  assert np.shape(_UpperCAmelCase   )[0] == np.shape(_UpperCAmelCase   )[0]
  assert _is_matrix_spd(_UpperCAmelCase   )

  # Initialize solution guess, residual, search direction.
  A_    :			Optional[int]									=    np.zeros((np.shape(_UpperCAmelCase   )[0], 1)   )
  A_    :			Dict									=    np.copy(_UpperCAmelCase   )
  A_    :			List[str]									=    np.copy(_UpperCAmelCase   )

  # Set initial errors in solution guess and residual.
  A_    :			Tuple									=    1E9
  A_    :			List[Any]									=    1E9
  A_    :			Optional[Any]									=    1E9

  # Set iteration counter to threshold number of iterations.
  A_    :			str									=    0

  while error > tol:
    # Save this value so we only calculate the matrix-vector product once.
    A_    :			str									=    np.dot(_UpperCAmelCase					,   _UpperCAmelCase   )

    # The main algorithm.

    # Update search direction magnitude.
    A_    :			Dict									=    np.dot(ra.T					,   _UpperCAmelCase   ) / np.dot(pa.T					,   _UpperCAmelCase   )
    # Update solution guess.
    A_    :			Union[str, Any]									=    xa + alpha * pa
    # Calculate new residual.
    A_    :			Dict									=    ra - alpha * w
    # Calculate new Krylov subspace scale.
    A_    :			Any									=    np.dot(r.T					,   _UpperCAmelCase   ) / np.dot(ra.T					,   _UpperCAmelCase   )
    # Calculate new A conjuage search direction.
    A_    :			Optional[Any]									=    r + beta * pa

    # Calculate errors.
    A_    :			Union[str, Any]									=    np.linalg.norm(r - ra   )
    A_    :			str									=    np.linalg.norm(x - xa   )
    A_    :			str									=    np.maximum(_UpperCAmelCase					,   _UpperCAmelCase   )

    # Update variables.
    A_    :			str									=    np.copy(_UpperCAmelCase   )
    A_    :			Union[str, Any]									=    np.copy(_UpperCAmelCase   )
    A_    :			Union[str, Any]									=    np.copy(_UpperCAmelCase   )

    # Update number of iterations.
    iterations += 1
    if iterations > max_iterations:
      break

  return x





def 		UpperCAmelCase__						(	):






  """simple docstring"""





  A_    :			Dict									=    3
  A_    :			Optional[int]									=    _create_spd_matrix(_UpperCAmelCase   )
  A_    :			str									=    np.random.randn(_UpperCAmelCase					,   1   )
  A_    :			str									=    np.dot(_UpperCAmelCase					,   _UpperCAmelCase   )

  # Numpy solution.
  A_    :			Optional[Any]									=    np.linalg.solve(_UpperCAmelCase					,   _UpperCAmelCase   )

  # Our implementation.
  A_    :			str									=    conjugate_gradient(_UpperCAmelCase					,   _UpperCAmelCase   )

  # Ensure both solutions are close to x_true (and therefore one another).
  assert np.linalg.norm(x_numpy - x_true   ) <= 1E-6
  assert np.linalg.norm(x_conjugate_gradient - x_true   ) <= 1E-6


if __name__ == "__main__":
   import doctest

   doctest.testmod()
   test_conjugate_gradient()





"""simple docstring"""

from __future__ import annotations

def 		lowercase_   (		_UpperCAmelCase	,   _UpperCAmelCase	,   _UpperCAmelCase						):




	"""simple docstring"""






	assert (
	    c % greatest_common_divisor(_UpperCAmelCase	,   _UpperCAmelCase						) == 0
	)  # greatest_common_divisor(a,b) function implemented below
	((A_) ,			(A_) ,			(A_))	:					List[Any]						 =		extended_gcd(_UpperCAmelCase	,   _UpperCAmelCase						)  # extended_gcd(a,b) function implemented below
	A_	:					int						 =		c / d
	return (r * x, r * y)

def 		lowercase_   (		_UpperCAmelCase	,   _UpperCAmelCase	,   _UpperCAmelCase	,   _UpperCAmelCase = 2						):




	"""simple docstring"""






	((A_) ,			(A_))	:					Any						 =		diophantine(_UpperCAmelCase	,   _UpperCAmelCase	,   _UpperCAmelCase						)  # Initial value
	A_	:					Union[str, Any]						 =		greatest_common_divisor(_UpperCAmelCase	,   _UpperCAmelCase						)
	A_	:					List[str]						 =		a // d
	A_	:					str						 =		b // d

	for i in range(_UpperCAmelCase						):
		A_	:					int						 =		xa + i * q
		A_	:					str						 =		ya - i * p
		print(_UpperCAmelCase	,   _UpperCAmelCase						)

def 		lowercase_   (		_UpperCAmelCase	,   _UpperCAmelCase						):




	"""simple docstring"""






	if a < b:
		A_ ,			A_	:					Tuple						 =		b, a

	while a % b != 0:
		A_ ,			A_	:					int						 =		b, a % b

	return b

def 		lowercase_   (		_UpperCAmelCase	,   _UpperCAmelCase						):




	"""simple docstring"""






	assert a >= 0 and b >= 0

	if b == 0:
		A_ ,			A_ ,			A_	:					str						 =		a, 1, 0
	else:
		((A_) ,			(A_) ,			(A_))	:					List[str]						 =		extended_gcd(_UpperCAmelCase	,   a % b						)
		A_	:					Optional[int]						 =		q
		A_	:					Tuple						 =		p - q * (a // b)

	assert a % d == 0 and b % d == 0
	assert d == a * x + b * y

	return (d, x, y)


if __name__ == "__main__":
		from doctest import testmod

		testmod(name='diophantine', verbose=True)
		testmod(name='diophantine_all_soln', verbose=True)
		testmod(name='extended_gcd', verbose=True)
		testmod(name='greatest_common_divisor', verbose=True)





